What is 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|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. {{math-stub}} {{DEFAULTSORT:Cook-Levin theorem}} [[Category:Theoretical computer science]]