Let $M_U$ be an universal Turing machine which fulfills the following condition:

If $M$ running $x$ takes $f(x)$ space, then $M_U$ running on $\langle \langle M\rangle,x\rangle$ takes $(f(|x|))^3+2\cdot|x|+|\langle M\rangle|$ space.

Why can we conclude from the above that ${\sf Space}(n^2) \neq {\sf Space}(n^7)$?


I assume with ${\sf SPACE}$ you mean ${\sf DSpace}$. As usual for these types of hierarchy question you can use a diagonalization argument.

So build a machine $D$ that takes its input $w$ and then executes $M_u(\langle w ,w \rangle)$. While executing $M_u$ it checks also how much space is used and how many steps the machine $M_u$ has done. Then the result of $D$ is the following:

  • if $D$ used more than $n^2$ space than reject,
  • if $D$ does more than $2^{cn^2}$ steps then accept (in this case the simulation detected a cycle if $\langle w \rangle$ would be a $n^2$ space bounded TM),
  • if none of the above occurred, then accept if $M_u$ rejected, and reject if $M_u$ accepted.

You can say that $D(w)$ anti-simulates the machine $M_u(\langle w ,w \rangle)$, if $\langle w \rangle$ is in ${\sf DSpace}(n^2)$. Clearly, $\langle D\rangle$ is in ${\sf DSpace}(n^7)$. However, it cannot be in ${\sf DSpace}(n^2)$. If it would be then you get a contradiction at $D(\langle D \rangle)$.

  • $\begingroup$ Is there a reason why this doesn't also apply for $\mathsf{NSPACE}$? (i.e. $\mathsf{NSPACE}(n^{2}) \neq \mathsf{NSPACE}(n^{7})$)? $\endgroup$ – Luke Mathieson Dec 15 '12 at 15:11

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.