Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
Could you expand on the "closed under polynomial time reduction" implies "Space(n^2) contained in Space(n)" part? [In particular, I haven't read chapter 4, so not familiar with space reductions; but I don't immediately see why a polytime TM can map all of space(n^2) into space(n)]. Thanks! –  LowerBounds Feb 22 '11 at 11:02
    
Suppose you get an input string of size n which would be decided in space n^2. Now a polynomial time reduction can blow up this string to size n^2 - just adding zeros for example. This is called padding. But then there is a TM which will decide this in in linear time, since it can just skip the zeros and run the original string which takes n^2 space. But since we blew the string up to size n^2, this is linear in the new input. –  wood Feb 22 '11 at 11:10
    
@wood: Awesome, thanks for the clarification! –  LowerBounds Feb 22 '11 at 18:44

Scott Aaronson has a blog post, Sidesplitting Proofs, which is a highly recommended read for a variety of reasons. The first proof in the list, which is said to be folklore, is that E, the class of problems solvable in $2^{O(n)}$ time, is not equal to PSPACE. The key is again padding: if the two are equal, then E=EXP, and we derive a contradiction. Like in your case, which is bigger (if one is even contained in the other) is not known.

share|improve this answer
    
@Thierry : Nice, the blog post looks awesome! (Upvoted you; would accept your answer too for all the new techniques, but can only accept one.) –  LowerBounds Feb 22 '11 at 18:44

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.