By definition, a problem P is NPC if: a. P is in NP, and b. Every problem in NP can be converted to an instance of P. Consider any two problems in NPC, P and

By definition, a problem P is NPC if: a. P is in NP, and b. Every problem in NP can be converted to an instance of P. Consider any two problems in NPC, P and Q. Then each is in NP, and each can be converted to the other. They are therefore equivalent. QED.