Re:The polynomial algorithm for 3-SAT problem (or P=NP)
by acangiano on Wednesday January 19, 2011 @06:47PM
(#2121818)
> I don't think one example constitutes a conclusion.
You're wrong. 3-SAT is NP-complete.
Quoting Wikipedia:
"But if any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NP-complete problems are harder or more difficult than NP problems in general."
You're wrong. 3-SAT is NP-complete.
Quoting Wikipedia:
"But if any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NP-complete problems are harder or more difficult than NP problems in general."