show/hide this revision's text 2 added 284 characters in body

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!
show/hide this revision's text 1

NP not equal to SPACE(n)

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!