# if P=NP, why is P a subset of NPC? Assuming P = NP, why should P be a subset of NPC? Here is how I understand it:

1. P is a subset of NP

2. NPC is a subset of NP

if we solve an NP Complete problem on a deterministic machine in polynomial time then

1. NP is a subset of P

2. P=NP (from 1 and 3)

3. NPC is a subset of P (2 and 3)

But why is P a subset of NPC, if P = NP? This question has been asked before and the answers just pointed to the definitions of NP, P and NP-C. I have gone through the definitions but still require a detailed picture.

To be in NPC a problem, C, has to be in NP, and every problem in NP has to be polynomial-time reducible to C.

If P=NP every problem in NP can be solved in polynomial time.

This means that if P=NP, we can for most problems in P define the following reduction to C; Solve the problem in polynomial time, if the instance you are looking at returns true then reduce it to an input to C for which we know that C returns true - Otherwise reduce it to an input for C that we know returns false.

So for an example; if we take C to the problem of determining if a number is even. And we want to reduce the hamiltonian path problem. We solve the hamiltonian path problem; which we can do in polynomial time since we assume P=NP. If we find that a hamiltonian path exists we select 2 as input to C. If we find that no hamiltonian path exists then we select 1.

This of course fails if C always returns true, or always returns false, so those two problems, as noted by Tom, while part of P, can not be part of NPC. However, all other problems in P will be in NPC if P=NP.

• "all other problems in P will be in NPC if P=NP." Does that mean: ((P = NP) implies (3-SAT is polynomially reducible to 2-SAT))? My understanding: 2-SAT is NL-complete; it is not known to be P-complete – Words Like Jared Jul 13 '18 at 14:54
• @WordsLikeJared Yes. You first run an polynomial algorithm to solve the 3-sat problem. If P=NP then this is possible. If the 3-Sat is satisfiable you reduce it to (x and x), if it is not satisfiable you reduce it to (x and not x). This has little bearing on the P-completeness of 2-SAT. See my example in the answer and note that determining if a number is even is certainly not P-complete. – Taemyr Jul 13 '18 at 15:08
• Thank you! I understand your comment and answer, now. Your original answer was clear. I just didn't understand it, yet. (This approach to reduction "feels like" "cheating" though) – Words Like Jared Jul 16 '18 at 19:51

The premise of your question is false. If $P=NP$, then the middle drawing ("This is true...") is wrong and the third ("but why not this?") drawing is correct.

Assuming P = NP, why should P be a subset of NPC?

$P$ is not a subset of $NPC$, and this is unconditionally true.

There are two very trivial problems in $P$ that can never be $NP$-complete: the empty problem (where the answer is always "no"), and $\Sigma^*$ (the problem consisting of the set of all inputs, where the answer is always "yes"). These problems are not $NP$-complete because a reduction (showing $NP$-completeness) must map yes-instances to yes-instances and no-instances to no-instances, but if there do not exist any no- or yes-instances to begin with this is impossible.

• It should be noted that those are the only problems in P not in NPC. OP probably got their second drawing from places like wikipedia which opt for a simple drawing with an added text disclaimer like "(excluding the empty language and its complement, which belong to P but are not NP-complete)" – potestasity Jul 13 '18 at 9:34