MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Nice question! But likely more knowledgably answered at CSTheory StackExchange: – Joseph O'Rourke Feb 4 '12 at 2:28
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? – Joel David Hamkins Feb 4 '12 at 2:48
See also related question:… – Joel David Hamkins Feb 4 '12 at 2:50
@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. – Neel Krishnaswami Feb 5 '12 at 3:43
up vote 26 down vote accepted

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).

share|cite|improve this answer

If I understand the paper's abstract, Yes.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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