The Cook-Levin Theorem

The Cook-Levin Theorem shows that the problem of determining whether a complex computational puzzle can be solved quickly (called SAT, or Boolean satisfiability) is as hard as any problem in a broad category called NP. It means that if you could efficiently solve SAT, you could solve many other difficult problems efficiently too. This theorem was the first to prove that certain problems are inherently hard, establishing a foundation for understanding computational complexity and why some problems are challenging to solve quickly.