If $A\subseteq\mathbb{N}$ is recursively enumerable, then there is a $\Delta^0_0$ set $B\subseteq\mathbb{N}^2$ such that $A=\{x|\exists y\;(x,y)\in B\}$. $\Delta^0_0$ consists of exactly the sets in the linear time hierarchy. Are there weaker complexity classes like $L$, $NL$, or some finite level of the linear time hierarchy, that have the same relation to recursively enumerable sets? What about complexity classes that are independent of $LTH$, like (probably) $P$? Of course, I know we couldn't have a proof that the answers are no for these examples, since we don't even know that $L\subsetneq LTH$ or $LTH\nsubseteq P$, but conceivably some widely-believed conjecture could be shown to imply a negative answer.

In general, is there a known weakest natural complexity class with that property? (I don't actually know exactly what I mean by "natural" complexity class, but if arbitrary classes of sets of tuples of integers are considered as complexity classes, then it seems like the answer would inevitably be no for boring reasons.)


2 Answers 2


Every r.e. set is the coordinate projection of the predicate $$T_M=\{(x,w):\text{$w$ is an accepting run of $M$ on input $x$}\}$$ for some Turing machine $M$. Under a natural encoding of Turing machine configurations, this predicate is computable in uniform $\mathrm{AC}^0$. (It is also computable in deterministic linear time.) In fact, it is on the first level of the depth hierarchy within $\mathrm{AC}^0$, namely in coNLOGTIME (note that logarithmic time is defined using Turing machines with random access to input by means of an oracle-like query tape in order to be meaningful).

We can do even better using padding. Consider $$T_M^+=\bigl\{z=(x,w,p):|z|\ge2^{|x|+|w|}\land(x,w)\in T_M\bigr\}.$$ It is a standard exercise that a logarithmic-time TM can compute the length of its input, hence it can easily extract the part of the input that should correspond to $(x,w)$, and check whether it belongs to $T_M$. Since $T_M$ is computable in linear time, this makes $T_M^+$ computable in logarithmic time. That is, every r.e. set is a coordinate projection of a DLOGTIME predicate.

I am not aware of any smaller complexity class being studied. ($\mathrm{NC^0}$ is only meaningful for computing functions rather than predicates, and it is unclear how to make it uniform anyway. Even in the random-access Turing machine model, sub-logarithmic time trivializes as one needs time to write down indices of input positions.)

  • $\begingroup$ Where could I find an explanation of this? $\endgroup$ Sep 8, 2016 at 17:11
  • $\begingroup$ I added a bit more explanation. The argument is really simple once you familiarize yourself a little with the relevant complexity classes. $\endgroup$ Sep 8, 2016 at 17:33

If $A\subseteq\mathbb{N}$ is recursively enumerable, let $\varphi$ be a Turing machine such that $\varphi(n)\downarrow\iff n\in A$. Then let $B:=\{(n,2^t)|\varphi(n)\text{ halts in }t\text{ steps}\}$, with $2^t$ expressed in unary, so that it takes up $2^t$ space. Then $A=\{x|\exists y\;(x,y)\in B\}$, and membership in $B$ can be computed with linear time and log space.

Of course, then the next question is what about smaller complexity classes than $L$? But I don't know enough about small complexity classes to say anything about that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.