What techniques exist to show that a problem is not NP-complete? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T06:31:49Z http://mathoverflow.net/feeds/question/9221 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete What techniques exist to show that a problem is not NP-complete? Qiaochu Yuan 2009-12-18T01:44:23Z 2009-12-18T09:30:55Z <p>The standard way to show that a problem <strong>is</strong> NP-complete is to show that another problem known to be NP-complete reduces to it. That much is clear. Given a problem in NP, what's known about how to show that it is <strong>not</strong> NP-complete? </p> <p>(My real question is likely to be inappropriate for this site for one or more reasons; I'm curious about what a proof that factoring isn't NP-complete would look like.)</p> http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9225#9225 Answer by Greg Kuperberg for What techniques exist to show that a problem is not NP-complete? Greg Kuperberg 2009-12-18T02:06:24Z 2009-12-18T03:13:55Z <p>There are much stronger versions of the P vs. NP conjecture that complexity theorists often take as axioms, and that imply that many problems are not NP-complete. The most standard class of assumptions is the conjecture that the NP hierarchy does not collapse. You can define NP as the analysis of polynomially bounded solitaire games with complete information. For instance, generalized Sudoku is such a game and it is known to be NP-complete. The nth level of the polynomial hierachy $\Sigma^n P$ and $\Pi^n P$ can be similarly defined by games with $n$ half moves. For instance, suppose that in generalized Sudoku, there is an initial board, and I can first try to make you lose by filling in some of the squares, with restrictions. (Like say only the "red" squares, and only with certain numbers.) After that you can move. Then whether I can win is a natural problem in $\Sigma^2 P$.</p> <p>In particular, the assertion that the polynomial hierarchy PH does not collapse implies that NP does not equal co-NP. If a problem is both in NP and co-NP, it cannot be NP-complete without collapse. (Proof: If solitaire were equivalent to co-solitaire, than a game with two half moves would also be equivalent to solitaire.) A good near example is the graph isomorphism problem, which is in NP and co-AM. AM is like NP but with randomness; it is the model in which Arthur gets an adaptive proof in response to a randomized question and becomes statistically convinced. AM is not quite NP, but it is conjectured to be the same. So if you put two standard conjectures together, graph isomorphism is not NP-complete either. <strong>Edit:</strong> Ryan and Harrison both point out that <a href="http://portal.acm.org/citation.cfm?id=31202" rel="nofollow">Boppana, Håstad, and Zachos</a> proved that if NP is contained in co-AM, then PH is contained in $\Sigma^2 P$. I.e., the hierarchy would collapse at the second level whether or not AM = NP. In particular this applies to graph isomorphism.</p> <p>Problems in BQP, such as factoring, are strongly suspected not to be NP-complete either, but it is an open problem to show that that would imply that the polynomial hierarchy collapses. However, decision-based problems from factoring, such as whether a number is square-free, are known to be in both NP and co-NP. This was known earlier, but it follows particularly quickly from the fact that primality is in P, since that certifies a factorization. <strong>Addendum:</strong> Certification of factorization is equivalent to <a href="http://en.wikipedia.org/wiki/Primality%5Fcertificate" rel="nofollow">certification of primality</a>, which as David pointed was first proved by Vaughan Pratt.</p> http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9226#9226 Answer by David Eppstein for What techniques exist to show that a problem is not NP-complete? David Eppstein 2009-12-18T02:10:59Z 2009-12-18T02:10:59Z <p>The only sure way to show that a decision problem is not NP-complete is to prove that its answer is yes for all instances or no for all instances. Everything else depends on the assumption that P ≠ NP, because if P = NP then every nontrivial decision problem is NP-hard.</p> <p>That said, standard ways of convincing theoretical computer scientists that a problem is unlikely to be NP-complete are to find a polynomial-time algorithm for it, or to show that the complementary problem belongs to NP. Famously, for testing whether a number is composite (clearly in NP: just exhibit a factorization), Vaughan Pratt's paper "Every prime has a succinct certificate" (SIAM J. Comput. 1975) showed that it was unlikely to be NP-complete long before it was shown to be in P.</p> <p>Actually, now that I think about it, there is another way of proving that a problem is not NP-complete: prove that it's not in NP, for instance by showing that it's complete for a higher complexity class like NEXP that is known not to collapse down to NP.</p> http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9228#9228 Answer by Ryan O'Donnell for What techniques exist to show that a problem is not NP-complete? Ryan O'Donnell 2009-12-18T02:15:19Z 2009-12-18T02:15:19Z <p>There are several results along these lines known, all of which use one technique: You show that if the problem is NP-complete, then some very strongly believed complexity hypothesis fails. In the following explanations, an asterisk* means "unless an extremely strongly-believed complexity hypothesis (e.g., P $\neq$ NP) fails".</p> <p>Factoring is known to be not NP-complete.* One has to be slightly careful with Factoring for a technical reason: in its most natural version ("Given a number, factor it") it is not a "decision problem". A standard decision problem version is: "Given n, L, and U, is there a prime factor of n between L and U?" This is easily seen to be in NP -- a witness is just a factor of n between L and U. On the other hand, this problem is not* NP-complete because it is also in coNP: there is a witness that proves n has no prime factor between L and U, namely a prime factorization of n. So if Factoring were NP-complete then all problems in NP would be in coNP; i.e., NP=coNP. So the asterisk in this paragraph refers to the assumption NP $\neq$ coNP, which is extremely strongly believed.</p> <p>The Graph-Isomorphism problem is a more interesting example. Telling if two given graphs are isomorphic is obviously in NP (the witness is the isomorphism). But in addition, Graph-<em>Nonisomorphism</em> is "almost" in NP as well. Specifically, it is in the class AM, which is essentially "randomized NP". There is a constant-round randomized "interactive proof" that two graphs are not isomorphic. (Basically, if you put the two graphs behind your back, randomly relabel them, then show them to a prover and the prover can always tell you which is which, then you become convinced the graphs must be non-isomorphic.) From this it follows that Graph-Isomorphism is not NP-complete.* Because if it were, Graph-Nonisomorphism would be coNP-complete, and then all coNP problems would be in AM. And this is known to imply that "the polynomial time hierarchy collapses" (the Boppana-Hastad-Zachos Theorem), which is very widely believed not to happen.</p> <p>(By the way, I assumed you were mostly interested in problems that aren't NP-complete because they are (presumably) too easy. In the other direction, there are also problems that shouldn't be NP-complete because they are too hard; e.g., $\Sigma_2$-complete problems like, "Given a Disjunctive Normal Form formula $\phi$ and a number $s$, is there an equivalent DNF formula of size at most $s$?")</p> http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9229#9229 Answer by Harrison Brown for What techniques exist to show that a problem is not NP-complete? Harrison Brown 2009-12-18T02:19:28Z 2009-12-18T02:24:51Z <p>Okay, so here is what we <em>can</em> do, and this I'mma put in an answer, because it's something like an answer. If we assume something stronger than P \neq NP, like that the polynomial hierarchy doesn't collapse, then we can prove that some things aren't NP-complete.</p> <p>The best example of such a result (actually, it's the first one I thought of, although in retrospect I've seen the ones other people mentioned too) is that if graph isomorphism is NP-complete, the polynomial hierarchy collapses to the second level. I can't seem to find an online version of the paper in which this is proved (it's by Boppana et al.) but I believe the argument goes more or less as follows: Graph isomorphism is in NP, easily. Graph isomorphism is also in co-AM; if you don't know what this means or haven't seen the proof, basically it means that if you have two graphs and I tell you they're <em>not</em> isomorphic, you can check that I'm telling the truth probabilistically. How: ou secretly choose one of the two graphs, randomly permute its vertices, and send it to me; I tell you which one it is. If the graphs are isomorphic, I won't be able to give you the right answer more than half the time, but if they aren't isomorphic, I can always give you the right answer. (We're assuming here that I have unbounded computational power.)</p> <p>So we apply a derandomization result, to show that co-AM is contained in some level of the polynomial hierarchy (I think the second level), and then we're done.</p> <p>As far as I know this is the only method that gives these kinds of conditional results. The reason it works is that PH is robust against things like randomization, but of course we have to assume stronger conjectures in complexity theory, so there's definitely a tradeoff.</p> <p>Here's something else I just thought of: Is there anything known about what a conditional proof that a certain problem isn't NP-hard <em>can't</em> be? (Along the lines of relativization, etc.) It's not as straightforward as relativization, since all we want is a conditional proof, but it seems like an interesting question.</p> http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9253#9253 Answer by Ryan Williams for What techniques exist to show that a problem is not NP-complete? Ryan Williams 2009-12-18T09:30:55Z 2009-12-18T09:30:55Z <p>Here's one more pointer. Ladner's theorem states that if $P \neq NP$ then there is a problem in $NP$ which is not $NP$-complete. </p> <blockquote> <p>Richard E. Ladner: On the Structure of Polynomial Time Reducibility. J. ACM 22(1): 155-171 (1975)</p> </blockquote> <p>Unfortunately the known proofs of this result produce a fairly unnatural problem. The zombie-metaphorical explanation is you take the head and torso of an $NP$-complete set and surgically stick on arms and legs of a polynomial time computable set. (If that ain't unnatural, I don't know what is.)</p> <p>See <a href="http://oldblog.computationalcomplexity.org/media/ladner.pdf" rel="nofollow">this writeup</a> for two proofs.</p>