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 sid0 on Thursday January 20, 2011 @04:07AM (#2123130)
Though it's probably inaccurate, that's how I intuit the matter.

It's actually quite accurate, but you can do even better: any other NP problem can be "compiled down" to one 3-SAT statement.

[ Parent | on HN ]
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by wlievens on Thursday January 20, 2011 @06:58AM (#2123352)
You're obvisouly correct. "3-SAT statements" is pretty meaningless in this context since you want to satisfy one big consistent statement.
[ Parent | on HN ]