Exercise 3.2 of Computational Complexity, a Modern Approach states:


Prove: NP != SPACE(n) [Hint: we don't know if either is a subset of the other.]


I don't know how to solve this problem.
It's in the diagonalization chapter.


I've looked around google a bit, but it basically ends up linking back to the Arora/Barak book.


Anyone know how to attack this?


Thanks!


More generally: to prove a language to be uncommputable, I can use diagonalization -- but to prove that two sets of languages (Space(N) and NP) are different, when it's not known that either is contained in the other -- what techniques are there for these proofs?


Thanks again!



NP not equal to SPACE(n)
I think that a common technique for proving such statements is for example the following type:


One class shares a closure property, while the other cannot because of a hierarchy theorem.
Thus they cannot be equal.


In this particular case a proof could proceed along these lines: Since NP is closed under polynomial time reductions, so would SPACE(n), if they were equal. Then deduce that polynomial time reductions would imply that SPACE(n^2) is contained in SPACE(n), which is impossible by the space hierarchy theorem.


