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 polynomialtime reduction to at least some subset of NP problems? If such a problem were to exist, then NPC would be the null set.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is CookLevin theorem, look it up on Wikipedia. 

