the space hierarchy theorem

The space hierarchy theorem is the memory twin of the time hierarchy theorem, and it is, if anything, even cleaner. It says that genuinely more scratch memory lets a machine decide strictly more languages. Hand a machine a bigger work tape and there are problems it can now solve that no smaller-memory machine ever could. This is one of the few separations we can actually prove, the firm ground beneath the otherwise conjecture-filled map of complexity classes.

Formally, if f and g are space-constructible and g(n) is o(f(n)) (f grows strictly faster, with no log overhead needed this time), then SPACE(f(n)) strictly contains SPACE(g(n)). The proof is again diagonalization, now with a space counter instead of a clock. Build a machine D that simulates a given machine M on M's own description while marking off exactly f(n) cells and refusing to use more; if M halts within that space and accepts, D rejects, else D accepts. Then D needs a bit more than g(n) space and disagrees with every g(n)-space machine on its own code, so D's language is in SPACE(f) but not in SPACE(g). The reason space needs no extra log factor (unlike time) is that simulating a machine costs essentially no memory overhead, you can reuse the simulated tape directly.

From this we get rock-solid space separations: L is strictly contained in PSPACE, PSPACE is strictly contained in EXPSPACE, and in general the space ladder climbs forever. These are theorems, full stop. Honest caveat, and it is an important one: hierarchy theorems separate the SAME kind of resource at different amounts (more space versus less space). They do NOT separate space from time or deterministic from nondeterministic, so they leave the marquee questions, like whether L is strictly inside P, or P inside PSPACE, completely open. We can prove the ladder rises within one resource; comparing across resources is where our tools run out.