Cook–Levin theorem

The Cook–Levin theorem is a theorem from theoretical computer science, which says that the Boolean satisfiability problem is NP-complete. A deterministic Turing machine can change a problem in NP in polynomial time to the problem of determining whether a Boolean formula is satisfiable. An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. The same follows for any NP-complete problem.

The question of whether such an algorithm exists is called the P versus NP problem and it is widely considered the most important unsolved problem in theoretical computer science. The theorem is named after Stephen Cook and Leonid Levin, who first described it in the 1970s.

Cook–Levin Theorem Media

• 

  Commutative diagram showing Cook's reduction of M to SAT. Data sizes and program runtimes are colored in orange and green, respectively.

• 

  Schematized accepting computation by the machine M.