News for hackers. Stuff that matters.

A comment on The polynomial algorithm for 3-SAT problem (or P=NP). Parent comment

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by djtumolo on Thursday January 20, 2011 @11:31AM (#2124152)
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.
[ Parent | on HN ]
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by rincewind on Thursday January 20, 2011 @12:05PM (#2124261)
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

[ Parent | on HN ]
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by RiderOfGiraffes on Thursday January 20, 2011 @12:53PM (#2124507)
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.

[ Parent | on HN ]