Catalog · Theory of Computation Lecture 15 of 25 Lecture 16: Cook-Levin Theorem ← Previous Lecture 15: NP-Completeness Next → Lecture 17: Space Complexity, PSPACE, Savitch's Theorem ✓ Mark complete Materials Transcript (PDF) ↗ transcript