Cook-Levin theorem

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.