# Syntactically capturing complexity classes

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?

• I might have more to say about this later on when I'm less busy. In the mean time you might want to check out Stephen Bellantoni's thesis under Stephen Cook; or the paper the two wrote ams.org/mathscinet-getitem?mr=1190824 Feb 14, 2011 at 15:20

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$, but it gets rather messy, and you usually need to throw in closure under $AC^0$-reductions, which rather spoils the picture.

• Now that I've browsing some background this seems to be closest what I was looking for. Also this seems close to the direction François G. Dorais pointed in the comment to the question.
– user10891
Feb 15, 2011 at 12:02

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:

Is there a syntactic characterization for BPP, BQP, or QMA?

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

https://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.

• Thats an interesting construction, but it seems close to equal to what Grzegorczyk did when setting the growth-rate restriction. Actually this answer makes me to think how to make a distinction between semantic and syntactic restrictions in the first place.
– user10891
Feb 15, 2011 at 6:49

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.

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

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.