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 azakai on Wednesday January 19, 2011 @06:47PM (#2121821)
The existence of an algorithm to solve 3SAT in polynomial time is sufficient to prove P = NP, since 3SAT is NP-complete. That is, any NP problem can be reduced to solving 3SAT.
[ Parent | on HN ]
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by yhmv on Wednesday January 19, 2011 @09:26PM (#2122318)
Coq could be used to reduce automatically, and more!
[ Parent | on HN ]