Lecture 19 - The Hierarchy Theorems
(Skeleton for Fall 2026.)
More Resources, More Power
TODO: time and space hierarchy theorem statements; what "strictly more" buys us: P is strictly inside EXPTIME, so some walls ARE proven.
Diagonalization, One Last Time
TODO: the proofs diagonalize against all machines running within the smaller bound; close the loop to Lecture 2 and Lecture 11: one technique carried the whole course.
Limits of Diagonalization
TODO: relativization and the Baker-Gill-Solovay barrier (statement only); why P versus NP needs ideas beyond this course; where to go next (randomized classes, approximation, Arora-Barak).