0
$\begingroup$

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?

1 Answers 1

5

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).

  • 0
    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.2011-10-09