title: "Lecture 17 - coNP and Space Complexity"
unit: 3
lecture: 17

Lecture 17 - coNP and Space Complexity

(Skeleton for Fall 2026.)

coNP

TODO: complements of NP languages; TAUTOLOGY; the certificate asymmetry (short proof of yes versus short proof of no); NP equals coNP would be almost as surprising as P equals NP.

Measuring Space

TODO: SPACE(f(n)) and NSPACE(f(n)); space can be reused, time cannot; the sublinear regime and log-space (mention only).

Time versus Space

TODO: containments we can prove (P inside PSPACE, NP inside PSPACE); the picture of classes so far and which walls are proven versus conjectured.