The Cook–Levin theorem, established by Stephen Cook in 1971 and independently by Leonid Levin, is a fundamental result in computational complexity theory. It states that the Boolean satisfiability problem (SAT) is NP-complete. This means that SAT is at least as hard as any problem in the complexity class NP (nondeterministic polynomial time), and any problem in NP can be reduced to SAT in polynomial time.
Articles by others on the same topic
Every NP verifier can be compiled into a polynomial-size Boolean circuit whose inputs encode its certificate, and then into an equisatisfiable conjunctive normal form by a Tseitin transformation. This gives a polynomial-time many-one reduction from every NP language to SAT. Checking a guessed assignment proves membership, so SAT is NP-complete.
