MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the seemingly broad definition of NP, it is very interesting that one can prove that any member of NP can be reduced in polynomial time to any member of NPC. (I guess this is true by definition of NPC, so let me restate my question.) How does one prove that no NP problem exists for which there is no polynomial-time reduction to at least some subset of NP problems? If such a problem were to exist, then NPC would be the null set.

share|cite|improve this question
I don't understand your modified question. Of course every problem in NP can be reduced some subset of NP problems - it can be "reduced" to itself, and often to lots of other problems polynomially-equivalent to it. Why does that imply that NPC is empty? – Alon Amit Jun 17 '11 at 7:09
up vote 1 down vote accepted

This is Cook-Levin theorem, look it up on Wikipedia.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.