2

Let $P$ be the class of formal languages that have polynomial-time decider, i.e. for each $L\in P$ there exists a Turing-machine $T$ such that for each $w\in L$ machine $T$ decides if $w\in L$ in polynomial time wrt the length of $w$.

Is it possible to define a grammar (in any "reasonable" sense) that could be used to define exactly the languages in $P$?

  • 7
    Not sure about a grammar, but we know that P is equivalent to languages expressible using first order logic + a fixed point operator and ordering. – Suresh Venkat May 20 '11 at 14:10
  • 2
    Check http://cstheory.stackexchange.com/questions/12/correspondence-between-complexity-classes-and-logic, http://cstheory.stackexchange.com/questions/869/is-there-a-logic-without-induction-that-captures-much-of-p, and http://cstheory.stackexchange.com/questions/1897/is-there-a-natural-restriction-of-vo-logic-which-captures-p-or-np. – Tsuyoshi Ito May 20 '11 at 15:09
  • 2
    A related question asks about programming languages that implement P: http://cstheory.stackexchange.com/questions/5120/programming-languages-for-efficient-computation

    Some of those answer might be relevant

     – Artem Kaznatcheev May 21 '11 at 01:50
  • 4
    "Is it possible to define a grammar (in any "reasonable" sense) that could be used to define exactly the languages in ?" I think you are using "grammar" not in their standard meaning in the literature. I think the question is not clear, I can't see what would constitute an answer to your question. If you want something like primitive recursive functions that would capture $P$ then the answer is yes. Replace the recursion with bounded recursion on notation and it will capture exactly function in $P$. – Kaveh May 21 '11 at 06:01
  • Each language is defined by its own grammar. You seem to be asking for a meta-grammar that defines the grammars of the languages in P, if I understand correctly. – Antonio Valerio Miceli-Barone May 23 '11 at 12:42
  • Here is what grammar means. In formal languages a grammar generate a language, not a class of languages. But you are asking for a grammar for a class of languages ($P$) not just one language. I am guessing that you mean something like a syntax for a programming language, something like say C++. (btw, please read the FAQ if you haven't yet.) – Kaveh May 24 '11 at 01:19

2 Answers2

2

If you have notions of linear logic, you might want to have a look at the article Soft Linear Logic and Polynomial Time [1] that describes a variant of linear logic (some of the deduction rules have been modified) whose formulas are only provable by proof that are polynomial-time algorithm.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1196

Abstract: We present a subsystem of second order Linear Logic with restricted rules for exponentials so that proofs correspond to polynomial time algorithms, and vice-versa.

gallais
  • 635
  • 4
  • 14
2

If you are not talking about "a grammar", but rather a grammar formalism, or class of grammars, then this might be useful: the class of languages generated by Range Concatenation Grammars (RCG) is exactly PTIME (for a proof, see Bertsch and Nederhof; for an introduction to RCG, see various papers by Boullier or the Wikipedia article).

DaniCL
  • 172
  • 4
  • This looks very interesting. It seems to me that this construction somewhat blurs the difference between a syntactic method to define a language and a computational model (algorithm) to decide a language. –  May 23 '11 at 09:59