NP not equal to SPACE(n) - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T08:48:31Z http://mathoverflow.net/feeds/question/56265 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56265/np-not-equal-to-spacen NP not equal to SPACE(n) LowerBounds 2011-02-22T10:30:52Z 2012-07-06T23:35:11Z <p>Exercise 3.2 of Computational Complexity, a Modern Approach states:</p> <p>Prove: NP != SPACE(n) [Hint: we don't know if either is a subset of the other.]</p> <p>I don't know how to solve this problem. It's in the diagonalization chapter.</p> <p>I've looked around google a bit, but it basically ends up linking back to the Arora/Barak book.</p> <p>Anyone know how to attack this?</p> <p>Thanks!</p> <p>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?</p> <p>Thanks again!</p> http://mathoverflow.net/questions/56265/np-not-equal-to-spacen/56266#56266 Answer by wood for NP not equal to SPACE(n) wood 2011-02-22T10:48:33Z 2011-02-22T11:34:37Z <p>I think that a common technique for proving such statements is for example the following type:</p> <p>One class shares a closure property, while the other cannot because of a hierarchy theorem. Thus they cannot be equal.</p> <p>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.</p> http://mathoverflow.net/questions/56265/np-not-equal-to-spacen/56268#56268 Answer by Thierry Zell for NP not equal to SPACE(n) Thierry Zell 2011-02-22T11:34:39Z 2011-02-22T11:34:39Z <p>Scott Aaronson has a blog post, <a href="http://www.scottaaronson.com/blog/?p=392" rel="nofollow">Sidesplitting Proofs</a>, 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 <strong>E</strong>, the class of problems solvable in \$2^{O(n)}\$ time, is not equal to <strong>PSPACE</strong>. The key is again padding: if the two are equal, then <strong>E=EXP</strong>, and we derive a contradiction. Like in your case, which is bigger (if one is even contained in the other) is not known.</p> http://mathoverflow.net/questions/56265/np-not-equal-to-spacen/101545#101545 Answer by fathollah for NP not equal to SPACE(n) fathollah 2012-07-06T23:35:11Z 2012-07-06T23:35:11Z <p>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</p>