2
$\begingroup$

In this illustration, P and NPC are two disjoint set.

We know that NPC is non-empty. If P $\cap$ NPC $=\varnothing$, then there are elements in NP which are not in P. Doesn't this imply that P $\neq$ NP?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ You're right that the illustration you link to assumes that P ≠ NP. Note that on the P versus NP Wikipedia page, it has the caption "Diagram of complexity classes provided that P ≠ NP." $\endgroup$
    – Henry Cohn
    Commented Apr 21, 2014 at 12:10

1 Answer 1

Reset to default
1
$\begingroup$

If there is even a single NPC problem in P, then P = NP. NPC problems are defined to be the hardest problems in NP in a suitable sense: every other NP problem reduces to them in polynomial time.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .