3 ms·
Can you supply a link to the proof that all NPC problems are equivalent? I remember learning it, but I can't remember how it worked.
by djtumolo 16y ago
Can you supply a link to the proof that all NPC problems are equivalent? I remember learning it, but I can't remember how it worked.
- rincewind 16y agoThis in the definition of NPC. What you have to prove is that a language is in NPC. This was proved for SAT first: http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem http://en.wikipedia.org/wiki/NP_complete http://en.wikipedia.org/wiki/NP_complete
- RiderOfGiraffes 16y agoBy 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.