# A problem in NP but not NP-complete?

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.

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.

• 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$". – Martin Rosenau Jan 6 at 12:41
• @MartinRosenau No, what I wrote is correct: if every NP problem is NP-complete (that is,if NP=NP-complete), then P=NP trivially. – Noah Schweber Jan 6 at 13:39
• 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". – Martin Rosenau Jan 6 at 13:59
• 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. – Martin Rosenau Jan 6 at 14:03
• @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.) – Noah Schweber Jan 6 at 14:13