3 ms·
A P-complete programming language seems like an interesting concept in cases where you want to allow programmability but guarantee that running programs from id
by andrewflnr 9y ago
A P-complete programming language seems like an interesting concept in cases where you want to allow programmability but guarantee that running programs from idiots or hostile actors doesn't take too long. Is there any work in using Horn clauses as a sort of P-complete programming language, maybe a bit like Prolog? Or are there nicer P-complete problems that get the same effect?
- zmonx 9y agoDatalog is a syntactic subset of Prolog, and Datalog queries can be evaluated in polynomial time. This does not fully answer your question, but I hope it is useful for you as a starting point.