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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Try reading on Ladner's Theorem, to get a starting point on this: en.wikipedia.org/wiki/NP-intermediate $\endgroup$– ShaullJan 5, 2020 at 20:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
$\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$ Jan 6, 2020 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$ Jan 6, 2020 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$ Jan 6, 2020 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$ Jan 6, 2020 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$ Jan 6, 2020 at 14:13