1
$\begingroup$

Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.

$\endgroup$
10
$\begingroup$

As written, the question is a bit trivial: if NP = NP-complete, then since P $\subseteq$ NP we get P=NP since every problem in P would be NP-complete.

I suspect what's meant, though, is the following:

Suppose there are no NP-intermediate problems; that is, that every problem in NP is either in P or is NP-complete. What does that tell us about P vs. NP?

This is definitely not trivial, but the answer turns out to be the same: Ladner's theorem says that if there are no NP-intermediate problems then P=NP.

It's worth noting that Ladner's theorem is constructive in that Ladner provides a specific example of a language $X$ such that if P$\not=$NP then $X$ is NP-intermediate. (I'm not making the stronger claim that it doesn't need the excluded middle, although I suspect that's true.) Moreover, the proof is pretty short; see e.g. here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ About the first part of your answer: As far as I understood correctly, it should be: "If $NP\neq NP-complete$", not "If $NP=NP-complete$". $\endgroup$ – Martin Rosenau Jan 6 at 12:41
  • 1
    $\begingroup$ @MartinRosenau No, what I wrote is correct: if every NP problem is NP-complete (that is,if NP=NP-complete), then P=NP trivially. $\endgroup$ – Noah Schweber Jan 6 at 13:39
  • $\begingroup$ Of course, it is correct. However, I understood the original question in the way: "What if NP $\neq$ NP-complete" instead of "What if NP = NP-complete". $\endgroup$ – Martin Rosenau Jan 6 at 13:59
  • $\begingroup$ By the way: It is already known that NP $\neq$ NP-complete: The two "trivial" problems (result is always "true"/"false" independent of the input) are not NP-complete but they are in NP. $\endgroup$ – Martin Rosenau Jan 6 at 14:03
  • $\begingroup$ @MartinRosenau Note that the title was edited: the original title was "What if NP= NP-complete?," which is why I wrote that. (But you're right about the trivial problems, that was a silly moment for me - I'm used to Turing reductions, not many-one reductions.) $\endgroup$ – Noah Schweber Jan 6 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.