title: "Lecture 15 - NP-Completeness and the Cook-Levin Theorem"
unit: 3
lecture: 15

Lecture 15 - NP-Completeness and the Cook-Levin Theorem

(Skeleton for Fall 2026.)

Polynomial-Time Reductions

TODO: definition (drill it); how it differs from the mapping reductions of Lecture 12 (resource bound added); transitivity.

NP-Hardness and NP-Completeness

TODO: definitions; why one NP-complete problem in P collapses all of NP; the role of SAT as the first complete problem.

The Cook-Levin Theorem

TODO: SAT is NP-complete; the tableau proof at whiteboard depth (computation histories as boolean formulas); students should leave believing it, not reproducing it.