Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.