30
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ Nice question! But likely more knowledgably answered at CSTheory StackExchange: cstheory.stackexchange.com $\endgroup$
    – Joseph O'Rourke
    Commented Feb 4, 2012 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
    Commented Feb 4, 2012 at 2:48
  • 4
    $\begingroup$ See also related question: mathoverflow.net/questions/28056/… $\endgroup$
    – Joel David Hamkins
    Commented Feb 4, 2012 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
    Commented Feb 5, 2012 at 3:43

4 Answers 4

Reset to default
31
$\begingroup$

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

Improve this answer
$\endgroup$
8
$\begingroup$

If I understand the paper's abstract, Yes.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ SQL is famous for having greatly different runtimes depending on seemingly unimportant details in the call. $\endgroup$
    – isomorphismes
    Commented Jun 10, 2018 at 15:33
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .