Algorithms for NP-Hard Problems (Section 22.2: 3-SAT and the Cook-Levin Theorem)
Tim Roughgarden Lectures · 7:29
The Cook–Levin theorem is the starting point for NP-hardness: it proves that 3SAT (satisfiability with at most three literals per clause) is NP-hard, so later reductions can generate many more hard problems from that...