Describe the Cook-Levin theorem
The Cook-Levin Theorem, also known as the Cook's theorem, states that the Boolean satisfiability problem (SAT) is NP-complete. This means SAT is both in NP and as hard as any problem in NP, establishing that every problem in the class NP can be transformed into an instance of SAT in polynomial time. It was the first problem proven to be NP-complete, forming the foundation for the theory of NP-completeness.