Syntactically capturing complexity classes - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T20:50:56Z http://mathoverflow.net/feeds/question/55415 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes Syntactically capturing complexity classes Frank 2011-02-14T15:01:45Z 2011-03-03T11:07:22Z <p>Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that prints the definition for every function in $PR$.</p> <p>Now, we can build hierarchies in the set $PR$ by adding some semantic restrictions. For example Grzegorczyk created hierarchy $\{\mathcal{E}_i\}$ by restricting the rate of growth of the functions in each level.</p> <p>I found papers mentioning the fact that if we take the second level of Grzegorczyk-hierarchy and define $E_2 = \{ f\in\mathcal{E}_2| ran(f)\in\{0,1\}\}$ (i.e. give yet another semantic restriction), then $E_2$ encapsulates LINSPACE (to my understanding its not actually this straightforward, but the idea should come clear).</p> <p>In this construction we started defining functions syntactically and added some semantic constraints to come up with a class of functions computable in linear space. </p> <p>This motivates to ask if there exists any constructions which provide ways to deploy purely syntactic machinery to produce, say, all the Turing-machines that run in polynomial space / time / whatever complexity class? Or functions instead of Turing-machines?</p> <p>Is this even possible?</p> http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes/55418#55418 Answer by arsmath for Syntactically capturing complexity classes arsmath 2011-02-14T15:25:18Z 2011-02-14T15:25:18Z <p>This isn't exactly the same flavor as the results you mentioned, but there is an area known as <a href="http://en.wikipedia.org/wiki/Descriptive_complexity_theory" rel="nofollow">descriptive complexity</a> which tries to find syntactic characterizations of complexity classes in terms of properties definable in different logical languages.</p> <p><a href="http://en.wikipedia.org/wiki/Fagin%27s_theorem" rel="nofollow">Fagin's theorem</a> says that the class NP corresponds to existential second-order logic. It's sufficient to restrict yourself to graphs. In that case, computing a graph property is in NP if and only if it's given by an existential second-order formula.</p> <p>For P, there is a partial result that says in the presence of a linear order, P is equivalent to first-order logic with an additional <a href="http://en.wikipedia.org/wiki/Least_fixed_point" rel="nofollow">least fixed point</a> operator.</p> <p><a href="http://arxiv.org/abs/1001.2572" rel="nofollow">This paper</a> by Martin Grohe begins with a survey of the area.</p> http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes/55421#55421 Answer by Artem Kaznatcheev for Syntactically capturing complexity classes Artem Kaznatcheev 2011-02-14T16:14:07Z 2011-02-15T10:57:00Z <p>Many of the famous complexity classes are syntactic, for example P, NP, PP, PSPACE etc. For these classes (say syntactic class $X$) there exists a Turing Machine $MC$ that accepts/constructs the machines $M$ such that the languages accepted by each $M$ are in the complexity class $X$ and for every language $L \in X$ there is some $M$ constructed by $MC$ that accepts that language. </p> <p>For example, if we want to capture PSPACE, simple enumerate all pairs of Turing Machines $M'$ and polynomials $p(n)$, to construct your machine $M$ that takes input $x$, simple calculate the size $n = |x|$ and let $m = p(n)$. Simulate $M'$ on $x$, If it uses more than $m$ space or enters the same state in the $2^m$ possible states, then reject, else output the same as $M'$ does. </p> <p>This is in contrast to semantic classes like BPP, BQP, etc, for which we do not know such a syntactic classification. The following 3 questions deal with this issue:</p> <p><a href="http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma" rel="nofollow">http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma</a></p> <p><a href="http://cstheory.stackexchange.com/questions/4792/benefits-for-syntactic-and-semantic-classes" rel="nofollow">http://cstheory.stackexchange.com/questions/4792/benefits-for-syntactic-and-semantic-classes</a></p> <p><a href="http://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes" rel="nofollow">http://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes</a></p> <p>The background section of the first question (from which I adapted an example of a syntactic class) might shed more light on your question.</p> http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes/55430#55430 Answer by Andreas Blass for Syntactically capturing complexity classes Andreas Blass 2011-02-14T17:39:31Z 2011-02-14T17:39:31Z <p>One example of the sort of result you want is "An algebra and a logic for NC" by Kevin Compton and Claude Laflamme (Information and Computation 87 (1990) 241-263.</p> http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes/55433#55433 Answer by Emil Jeřábek for Syntactically capturing complexity classes Emil Jeřábek 2011-02-14T18:22:48Z 2011-02-14T18:22:48Z <p>If you are interested in characterizations using recursion operators like in the definition of primitive recursive functions or the Grzegorczyk hierarchy, Cobham characterized P (or rather, FP, as a class of functions on binary strings) as the closure of a handful of initial functions under composition and limited recursion on notation: the latter allows to construct a new function $f$ on binary strings from functions $g,h_0,h_1,k$ by</p> <p><code>\begin{align*}f(\epsilon,\vec y)&amp;=g(\vec y)\\f(x\smallfrown a,\vec y)&amp;=\operatorname{Tr}(h_a(x,\vec y,f(x,\vec y)),k(x,\vec y))\end{align*}</code></p> <p>where $\operatorname{Tr}(x,y)$ is string $x$ truncated to at most $|y|$ bits.</p> <p>You can obtain PSPACE by modifying $E_2$ so that you include among the initial functions some function of polynomial growth (in terms of bit length), such as <code>$f(x)=2^{|x|^2}$</code>. It is possible to give a characterization using some sort of recursion for classes like L, $NC^1$, or $AC^0[2]$, but it gets rather messy, and you usually need to throw in closure under $AC^0$-reductions, which rather spoils the picture.</p> http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes/57240#57240 Answer by none for Syntactically capturing complexity classes none 2011-03-03T11:07:22Z 2011-03-03T11:07:22Z <p>Bellantoni and Cook's syntactic characterization of P, and Bellantoni's 1992 thesis should probably be mentioned:</p> <ul> <li><a href="http://www.cs.toronto.edu/~sacook/homepage/ptime.pdf" rel="nofollow">http://www.cs.toronto.edu/~sacook/homepage/ptime.pdf</a></li> <li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.8024" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.8024</a></li> </ul>