Cook-Levin theorem

In computational complexity theory, the Cook-Levin theorem is a seminal theorem that states that the Boolean satisfiability problem (SAT) is NP-complete.

One key implication of this is that we can prove the NP-completeness of other problems via a polynomial time reduction to SAT.