HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

if P=NP, why is P a subset of NPC?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
npcwhysubset

Problem

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

-
P is a subset of NP

-
NPC is a subset of NP

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

-
NP is a subset of P

-
P=NP (from 1 and 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.

Solution

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.

Context

StackExchange Computer Science Q#94201, answer score: 9

Revisions (0)

No revisions yet.