Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


This 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/NP_complete


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: