Space hierarchy theorem

The space hierarchy theorem is the spatial analogue of the time hierarchy theorem in computational complexity theory. It states that for any space-constructible function f(n) ≥ log n, there exist problems solvable in O(f(n)) space that cannot be solved in o(f(n)) space. The proof uses the same diagonalization technique: a universal machine simulates all machines using less space and flips the answer. The space hierarchy theorem separates L from PSPACE and PSPACE from EXPSPACE, but like its temporal counterpart, it fails to separate adjacent classes within the polynomial hierarchy — such as L from NL or NL from P. The theorem reveals that space, like time, is a resource that yields strictly more computational power when generously allotted, but the incremental separations that would reshape cryptography and algorithmics remain beyond its reach.