Editing Cook–Levin theorem (section)

==Consequences==
The proof shows that every problem in NP can be reduced in polynomial time (in fact, [[logarithmic space]] suffices) to an instance of the Boolean satisfiability problem. This means that if the Boolean satisfiability problem could be solved in polynomial time by a [[deterministic Turing machine]], then all problems in NP could be solved in polynomial time, and so the [[complexity class]] NP would be equal to the complexity class P.

The significance of NP-completeness was made clear by the publication in 1972 of [[Richard Karp]]'s landmark paper, "Reducibility among combinatorial problems", in which he showed that [[Karp's 21 NP-complete problems|21 diverse combinatorial and graph theoretical problems]], each infamous for its intractability, are NP-complete.<ref name="Karp">{{cite book |last=Karp |first=Richard M. |title=Complexity of Computer Computations |publisher=Plenum |year=1972 |isbn=0-306-30707-3 |editor=Raymond E. Miller |location=New York |pages=85–103 |chapter=Reducibility Among Combinatorial Problems |author-link=Richard Karp |editor2=James W. Thatcher |chapter-url=}}</ref>

Karp showed each of his problems to be NP-complete by reducing another problem (already shown to be NP-complete) to that problem.  For example, he showed the problem 3SAT (the [[Boolean satisfiability problem]] for expressions in [[conjunctive normal form]] (CNF) with exactly three variables or negations of variables per clause) to be NP-complete by showing how to reduce (in polynomial time) any instance of SAT to an equivalent instance of 3SAT.<ref>First modify the proof of the Cook–Levin theorem, so that the resulting formula is in conjunctive normal form, then introduce new variables to split clauses with more than 3 atoms.  For example, the clause <math>(A \lor B \lor C \lor D)</math> can be replaced by the conjunction of clauses <math>(A \lor B \lor Z) \land (\lnot Z \lor C \lor D)</math>, where <math>Z</math> is a new variable that will not be used anywhere else in the expression.  Clauses with fewer than three atoms can be padded; for example, <math>(A \lor B)</math> can be replaced by <math>(A \lor B \lor B)</math>.</ref>

Garey and Johnson presented more than 300 NP-complete problems in their book ''Computers and Intractability: A Guide to the Theory of NP-Completeness'',<ref>{{Garey-Johnson}}</ref> and new problems are still being discovered to be within that complexity class.

Although many practical instances of SAT can be [[Boolean satisfiability problem#Algorithms for solving SAT|solved by heuristic methods]], the question of whether there is a deterministic polynomial-time algorithm for SAT (and consequently all other NP-complete problems) is still a famous unsolved problem, despite decades of intense effort by complexity theorists, [[mathematical logician]]s, and others.  For more details, see the article [[P versus NP problem]].