12
$\begingroup$

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!

$\endgroup$

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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! $\endgroup$ Feb 22, 2011 at 11:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – wood
    Feb 22, 2011 at 11:10
  • $\begingroup$ @wood: Awesome, thanks for the clarification! $\endgroup$ Feb 22, 2011 at 18:44
  • $\begingroup$ see: csie.ntu.edu.tw/~lyuu/complexity/2010/20101026s.pdf for full proof. $\endgroup$
    – Nahum
    Jun 12, 2016 at 6:25
  • $\begingroup$ Can you modify this to show that $L\ne NTIME(n)$? $\endgroup$ Feb 15, 2018 at 18:33
9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @Thierry : Nice, the blog post looks awesome! (Upvoted you; would accept your answer too for all the new techniques, but can only accept one.) $\endgroup$ Feb 22, 2011 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.