Is it correct to say that $P=NP$ implies $P=NPC$?

I was reviewing the definition of NP-complete and I noticed this diagram which states that if $P=NP$, then $P=NP=NPC$. However, it seems to me that if $P=NP$, then $NPC=NP \setminus \{\mathbb{N},\emptyset\}$, because there can't be a reduction from a problem with two possible solutions to a problem with only one possible solution, as seems to be required by the definitions. So which statement is correct? Is this a case of loose terminology similar to the issue of whether or not zero should be considered a "natural number"? Or maybe the diagram is right and there is something else wrong with my understanding of the definitions?


Your understanding is correct. The diagram is just ignoring the two trivial cases.

Alternatively, one could define a "polynomial-time reduction" such that it was allowed, but not required, to produce a final answer immediately instead of an instance of the next problem in the chain. In that case the diagram would be right (and the modification would really not affect anything else).

  • $\begingroup$ Also we could define P and NP to not include $\emptyset$ and $\mathbb{N}$, or define "decision problem" that way. I wonder what are the most productive definitions to use for common problems? $\endgroup$ – Dan Brumleve Oct 9 '11 at 0:44
  • $\begingroup$ That would be very inconvenient. There are lots of places in theory where one wants the main complexity classes to be closed under reasonable "strictly easier to decide than" relations, and having to make explicit exceptions for the trivial problems each time would be prohibitively cumbersome -- especially given that the only advantage would be that in a particular hypothetical future we would have a slightly simpler characterization available for NPC which in that same hypothetical future had become a completely irrelevant class. $\endgroup$ – Henning Makholm Oct 9 '11 at 1:07
  • $\begingroup$ Do you think that using an expanded definition of "reducible" is the best way to go, rather than modifying "P" or "NP" or "decision problem"? The wiki definition supposes a chain with length exactly one and that inconveniently conflicts with the diagram. Another option is defining NPC explicitly to include $\mathbb{N}$ and $\emptyset$? $\endgroup$ – Dan Brumleve Oct 9 '11 at 1:16
  • $\begingroup$ Personally I don't think it's a problem worth solving. It's not even potentially relevant -- as long as we don't know that P=NP there are much more significant gaps than the two trivial cases, and if it ever turns out that P=NP, then there will be no reason to ever speak about NP-complete problems as a class again anyway. $\endgroup$ – Henning Makholm Oct 9 '11 at 1:20

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.