The polynomial algorithm for 3-SAT problem (or P=NP)

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by wlievens on Thursday January 20, 2011 @03:33AM (#2123088)

Here's how I intuit this: 3-SAT is like "machine language" for other NP problems. Any other NP problem can be "compiled down" to 3-SAT statements.

Though it's probably inaccurate, that's how I intuit the matter.

[ Parent | on HN ]

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 ]