title: "Lecture 13 - Time Complexity and the Class P"
unit: 3
lecture: 13

Lecture 13 - Time Complexity and the Class P

(Skeleton for Fall 2026.)

Measuring Time

TODO: running time of a TM; worst case (callback to Lecture 4); TIME(t(n)) as a complexity class, finally cashing in the Unit 0 promise.

Model Robustness

TODO: polynomial slowdown between reasonable models (multitape versus single tape); why polynomial time is model-independent and therefore a good class boundary.

The Class P

TODO: definition (drill it); example problems in P (PATH, relative primality, CFL membership via dynamic programming); the extended Church-Turing thesis and its cracks (quantum aside).