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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

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

Improve this answer
$\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$
    – LowerBounds
    Commented Feb 22, 2011 at 18:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .