Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

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)$?

share|cite|improve this question
up vote 3 down vote accepted

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)$.

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

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.