Welcome to MathOverflow

Question

4

1

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!

edited Feb 22 2011 at 10:38

asked Feb 22 2011 at 10:30

LowerBounds
473●2●12

wood · Accepted Answer · 2011-02-22 11:34:37Z UTC

6

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.

edited Feb 22 2011 at 11:34

answered Feb 22 2011 at 10:48

wood
1,211●5●16

	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 2011 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 2011 at 11:10
	@wood: Awesome, thanks for the clarification! – LowerBounds Feb 22 2011 at 18:44

Thierry Zell · Answer 2 · 2011-02-22 11:34:39Z UTC

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.

fathollah · Answer 3 · 2012-07-06 23:35:11Z UTC

-1

this prob is hard we dont know nL!=np and dont know np!=pspace if u have l in np and not in space(n) you proved np!=nl if u have l in space(n) and not in np you proved np!=pspace

answered Jul 6 at 23:35

fathollah

community wiki

NP not equal to SPACE(n)

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.