StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>To give you the essence of the proof (which is several pages of hard going in Garey & Johnson's <em>Computers and Intractibility</em>):</p> <p>Any computational problem can be expressed as a Turing machine.</p> <p>It is possible to express the Turing machine as a logic problem, satisfying certain complexity constraints.</p> <p>Therefore, if you can solve the logic problem in polynomial time, you can solve the Turing machine problem in polynomial time.</p> <p>This (along with some other considerations) shows that if you can solve the logic problem in polynomial time, you can solve any NP problem in polynomial time. This being the definition of NP-complete, the logic problem is therefore NP-complete, and can be used as a basis for other problems.</p> <p>The logic problem used is called Satisfiability (often abbreviated to SAT). Given a series of clauses of the form (A or not-B or not-C) (clauses consisting of any number of propositions and negations of propositions connected by logical or), is there an assignment of truth values to the propositions that makes all the clauses true?</p> <p>NP-completeness is a well-defined property. The only reason you'd be in doubt about a problem being NP-complete is that you thought you could reduce another NP-complete problem to it, but haven't managed to find a convenient problem or derive a proof yet.</p> <p>The question is not whether NP-complete problems exist, or how to prove a problem is NP-complete, but what that means. Nobody has yet produced a polynomial-time algorithm to solve an NP-complete problem, and nobody has proved that such an algorithm can't exist. Whether or not P=NP, we certainly don't have good algorithms to solve any NP-complete problem.</p> <p>This is one of the Claypool Foundation's Millenium Problems, so if you can come up with a proof that has been eluding some very bright people for quite a few years, there's a million dollars in it for you.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload