17
$\begingroup$

The standard way to show that a problem is 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 not NP-complete?

(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.)

$\endgroup$
5
  • 4
    $\begingroup$ Well, the "duh answer" is that we don't have any such techniques, since if P = NP every problem (with I think a couple of trivial exceptions) is NP-complete! But this presumably isn't what you want. That said, I don't think that there are any natural problems outside of P that we can show are not NP-complete even assuming P \neq NP. $\endgroup$ Dec 18, 2009 at 1:51
  • $\begingroup$ Er, in the first sentence above I of course mean "every problem in NP." And I sort of assumed you knew this, but just in case, here's the unnatural problem we can show isn't NP-complete (assuming P \neq NP): oldblog.computationalcomplexity.org/archive/… $\endgroup$ Dec 18, 2009 at 1:56
  • 1
    $\begingroup$ A proof that factoring isn't NP-complete will appear only after we show that P is not equal to NP. We might live long enough to see such a proof. $\endgroup$
    – Rune
    Dec 18, 2009 at 4:40
  • $\begingroup$ I meant to say we might not live long enough to see such a proof. $\endgroup$
    – Rune
    Dec 18, 2009 at 4:51
  • 6
    $\begingroup$ @Rune: I agree that we may or may not live long enough to see such a proof. :-) $\endgroup$ Dec 18, 2009 at 7:55

5 Answers 5

11
$\begingroup$

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$.

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. Edit: Ryan and Harrison both point out that Boppana, Håstad, and Zachos 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.

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. Addendum: Certification of factorization is equivalent to certification of primality, which as David pointed was first proved by Vaughan Pratt.

$\endgroup$
2
  • $\begingroup$ Actually, I could be making a stupid mistake here, but if you randomize some class in the polynomial hierarchy, won't the resulting class be contained in a higher level? (Following from the fact that BPP is in the second level of PH.) So if you believe the polynomial hierarchy doesn't collapse, you can use randomness as much as you want, which I implied in my answer. $\endgroup$ Dec 18, 2009 at 16:21
  • $\begingroup$ That by itself does not equate two levels of PH with each other. What is more to the point is that AM is only barely different from NP. The merit of the BHZ paper is to replace these frustrating partial arguments with one that works. $\endgroup$ Dec 18, 2009 at 16:43
20
$\begingroup$

Here's one more pointer. Ladner's theorem states that if $P \neq NP$ then there is a problem in $NP-P$ which is not $NP$-complete.

Richard E. Ladner: On the Structure of Polynomial Time Reducibility. J. ACM 22(1): 155-171 (1975)

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.)

See this writeup for two proofs.

$\endgroup$
1
  • 4
    $\begingroup$ +1 for the funniest explanation of Ladner's theorem I've ever heard. $\endgroup$ Dec 18, 2009 at 9:54
12
$\begingroup$

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".

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.

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-Nonisomorphism 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.

(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$?")

$\endgroup$
8
$\begingroup$

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.

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.

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.

$\endgroup$
1
$\begingroup$

Okay, so here is what we can 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.

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 not 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.)

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.

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.

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 can't 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.

$\endgroup$

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.