View source for 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.

[[Category:Mathematics]]
[[Category:Systems]]