Syntactically capturing complexity classes - MathOverflow

Syntactically capturing complexity classes

2011-02-14T15:01:45Z

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

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.

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

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.

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?

Is this even possible?

Answer by arsmath for Syntactically capturing complexity classes

2011-02-14T15:25:18Z

This isn't exactly the same flavor as the results you mentioned, but there is an area known as descriptive complexity which tries to find syntactic characterizations of complexity classes in terms of properties definable in different logical languages.

Fagin's theorem 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.

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 least fixed point operator.

This paper by Martin Grohe begins with a survey of the area.

Answer by Artem Kaznatcheev for Syntactically capturing complexity classes

2011-02-14T16:14:07Z

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.

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.

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:

http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma

http://cstheory.stackexchange.com/questions/4792/benefits-for-syntactic-and-semantic-classes

http://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes

The background section of the first question (from which I adapted an example of a syntactic class) might shed more light on your question.

Answer by Andreas Blass for Syntactically capturing complexity classes

2011-02-14T17:39:31Z

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.

Answer by Emil Jeřábek for Syntactically capturing complexity classes

2011-02-14T18:22:48Z

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

$$\begin{align*}f(\epsilon,\vec y)&=g(\vec y)\\f(x\smallfrown a,\vec y)&=\operatorname{Tr}(h_a(x,\vec y,f(x,\vec y)),k(x,\vec y))\end{align*}$$

where $\operatorname{Tr}(x,y)$ is string $x$ truncated to at most $|y|$ bits.

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 $f(x)=2^{|x|^2}$ . 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.

Answer by none for Syntactically capturing complexity classes

2011-03-03T11:07:22Z

Bellantoni and Cook's syntactic characterization of P, and Bellantoni's 1992 thesis should probably be mentioned: