MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I don't get it; doesn't the class R contains all the recursive languages? – Hsien-Chih Chang 張顯之 Mar 21 '11 at 10:06
The author means a complexity class in the sense of Blum - – François G. Dorais Mar 21 '11 at 10:38
Thank you François! – Hsien-Chih Chang 張顯之 Mar 21 '11 at 11:02
Have you looked at ? – András Salamon Mar 21 '11 at 22:49
Thanks for your answer András but I really can't see how the speed up theorem implies that C can't exist. – Niki Mar 22 '11 at 15:34
up vote 3 down vote accepted

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.

share|cite|improve this answer
Thank you Marios! – Niki Apr 1 '11 at 0:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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