# A programming language that can only create algorithms with polynomial runtime?

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.

-
Nice question! But likely more knowledgably answered at CSThoery StackExchange: cstheory.stackexchange.com –  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: mathoverflow.net/questions/28056/… –  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

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.

-