What was the first problem proven to be NP-complete by Stephen Cook and Leonid Levin?
Show answer
Boolean Satisfiability (SAT)
The Cook-Levin theorem proved that SAT is NP-complete, meaning any problem in NP can be reduced to it in polynomial time. This established the foundation for the theory of NP-completeness.
Also asked as:
- Which problem was the first to be proven NP-complete by Cook and Levin?