I want to prove that there does not exist some complexity class that contains all recursive languages.

Any complexity class C is defined by a complexity measure $\Phi$ (according to Blum axioms) and a total recursive function f:N $\rightarrow$ N. So there does not exists C that contains all languages L for which there exists a Turing Machine M that decides L and for all x $\Phi$(M,x)<=f(|x|).

Any ideas?


Let $\langle M_i\rangle$ be an enumeration of all Turing Machines (TM) and $\langle f_i\rangle$ the corresponding ($f_i=f_{M_i}$) enumeration of the functions in $RE$. Suppose there is an $f\in REC$ such that all the recursive languages are in the complexity class $\mathcal{C}(f)=${$f_i\in RE:\forall x\ \Phi(i,x)\leq f(x)$}.

Here are two ways you can prove this is not possible:

1) $\Phi(i,x)=y$ is $REC$, thus let $N$ be the TM which computes it. We can use $N$ to construct a new TM $N'$ which takes as input $i$, then calculates $\Phi(i,x)=y$ for every $x$ and all $y\leq f(x)$ and it halts iff for some $x$, $\Phi(i,x)=y$ is false for all $y\leq f(x)$ or $rng(f_i(x))\nsubseteq${$0,1$}.

Having a closer look on $N'$, we see that it recognizes exactly the language

$TOT'=${$i\in\mathbb{N}:f_i\mbox{ not total}\vee f\mbox{ is not a relation}$}.

Thus $TOT'\in RE$ which can not be true because it is $\Sigma_2$-complete. ($\Sigma_2$ contains the relations which are $RE$ given a $co-RE$ oracle).

2) We use the Recursive Relatedness Theorem, i.e.

Suppose $\Phi,\Psi$ be complexity measures. Then there exists an $r(x,y)\in REC$ s.t.:

(i) $\forall x,y\ r(x,y)< r(x,y+1)$;

(ii) $\forall i\ \forall^* x\ \Phi(i,x)\leq r(x,\Psi(i,x))$; ($\forall^*$ means for all but finitely many)

(iii) $\forall i\ \forall^* x\ \Psi(i,x)\leq r(x,\Phi(i,x))$.

(This says roughly that the one measure is bounded by the other using a REC function.)

Let $\Phi$ be the measure under consideration and $T$ the usual masure of time complexity. By (iii), $T(i,x)\leq r(x,\Phi(i,x))$ and since $r$ is increasing for $y$ and $\Phi(i,x)\leq f(x)$, we get that $T(i,x)\leq r(x,f(x))$ for all $i$ s.t. $f_i\in \mathcal{C}(f)$.

$r(x,f(x))$ is recursive hence we can get a TM $M_{i_0}$ which given an input $x$ moves $r(x,f(x))+1$ times and halts with output $0$. $f_{i_0}$ realizes a recursive language so it is in $\mathcal{C}(f)$, which means that $\forall^* x\ r(x,f(x))+1=T(i_0,x)\leq r(x,f(x))$. But this is a contradiction.

If you want to see the proof that $TOT'$ is $\Sigma_2$-complete (actually that $TOT=\mathbb{N}\setminus TOT'$ is $\Pi_2$-complete. $TOT$ contains functions instead of relations but you can easily reduce the one to the other) you can check it in p.224 of Computability, complexity and languages of Martin Davis.

Inside the same book, you can find the proof of the recursive relatedness theorem in p.422. Actually the whole chapter (14) contains some useful results on abstract complexity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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