Cook–Levin theorem

The Cook–Levin theorem states that Boolean satisfiability is NP-complete: every problem in NP can be reduced to it in polynomial time.

Boolean satisfiability problem: The decision problem of whether a Boolean formula has an assignment that makes it true. The theorem proves this problem NP-complete by encoding computations as formulas.
NP-hardness: A property of a problem to which every problem in NP can be reduced in polynomial time. The reduction establishes this property for satisfiability.
Stephen Cook: A Canadian-American computer scientist whose work founded key parts of computational complexity theory. His 1971 paper proved satisfiability NP-complete.
Karp's 21 NP-complete problems: A list of 21 combinatorial problems shown NP-complete by Richard Karp in 1972. Karp reduced satisfiability to a broad collection of problems.
NP: The complexity class of decision problems whose yes-instances have polynomial-size certificates verifiable in polynomial time. The reduction starts with an arbitrary problem in this class.
NP-completeness: The property of being both in NP and NP-hard. The theorem's conclusion combines hardness with efficient verification.
Leonid Levin: A Soviet and Russian mathematician and computer scientist known for foundational work in computational complexity. He independently established a related universality result for search problems.
3-SAT: The satisfiability problem for Boolean formulas in conjunctive normal form with three literals per clause. It is a restricted satisfiability variant that remains NP-complete.
Turing machine: An abstract computational model that reads and writes symbols on a tape according to finite transition rules. A machine's bounded computation supplies the configurations encoded by the formula.
Certificate (complexity theory): A polynomial-size witness that allows a verifier to confirm a yes-instance in polynomial time. Satisfying assignments act as certificates for satisfiable formulas.

Linked from 13 pages