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 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 ]

There are no comments on this comment yet.