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

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?

• 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? – Dan Brumleve Oct 9 '11 at 0:44
• 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$? – Dan Brumleve Oct 9 '11 at 1:16