Cook–Levin theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Cook–Levin theorem is a theorem from theoretical computer science, which says that the Boolean satisfiability problem is NP-complete. Any problem that is in NP can be changed so that to the Boolean satisfiability theorem. On a deterministic Turing machine this takes polynomial time. 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.