4
$\begingroup$

venn diagram of P and NP

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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 $\endgroup$ – Words Like Jared Jul 13 '18 at 14:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Taemyr Jul 13 '18 at 15:08
  • $\begingroup$ 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) $\endgroup$ – Words Like Jared Jul 16 '18 at 19:51
7
$\begingroup$

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.

$\endgroup$
  • 11
    $\begingroup$ 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)" $\endgroup$ – potestasity Jul 13 '18 at 9:34

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.