Has someone constructed a programming language that can construct all the algorithms in P, and no others?

I'm interested in this restriction coming from the syntax naturally, as opposed to just being a normal Turing machine with a step-timer attached.

  • 7
    $\begingroup$ Nice question! But likely more knowledgably answered at CSTheory StackExchange: cstheory.stackexchange.com $\endgroup$ – Joseph O'Rourke Feb 4 '12 at 2:28
  • 3
    $\begingroup$ Why do you object to the step-timer method? Doesn't this provide a way of satisfying your formal requirement syntactically, while also clearly computing exactly the polynomial time algorithms? $\endgroup$ – Joel David Hamkins Feb 4 '12 at 2:48
  • 4
    $\begingroup$ See also related question: mathoverflow.net/questions/28056/… $\endgroup$ – Joel David Hamkins Feb 4 '12 at 2:50
  • 1
    $\begingroup$ @Joel: the motivation is perhaps clearest in the case of logspace. If $f$ and $g$ are logspace-computable, then so is $f \circ g$, but the implementation of this is surprisingly delicate, since you have to dovetail the execution of $f$ and $g$ to incrementally produce the bits of $g$'s output to feed to $f$. So it's natural to look for programming languages/logics where the composition operation is algebraically well-behaved and does not require any tricky coding games. $\endgroup$ – Neel Krishnaswami Feb 5 '12 at 3:43

Yes, there is a whole research area devoted to this problem -- it's called "implicit complexity theory". The general idea is to use a lambda calculus based on linear logic. The linearity constraint on lambda-terms lets you control the complexity of cut-elimination (and hence of evaluation), giving natural programming languages that are complete for various complexity classes (such as PTIME, PSPACE, or LOGSPACE).


If I understand the paper's abstract, Yes.


Perhaps the most natural examples come from various extensions to SQL (of course, if query languages count). For example Datalog on ordered relations equals P. Generally, such languages are somewhere around P, but for most of them it is really hard to give exact characterisations.

  • $\begingroup$ SQL is famous for having greatly different runtimes depending on seemingly unimportant details in the call. $\endgroup$ – isomorphismes Jun 10 '18 at 15:33

Yet another perspective (and IMHO a more natural one) is descriptive complexity theory (check also this Wikipedia article).

They study the question from a perspective different from the one mentioned by Neel. There are various languages that capture exactly the polynomial time computable functions. One of the most famous ones is FO+LFP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.