Space Hierarchy Theorem

The Space Hierarchy Theorem is a foundational result of computational complexity theory stating that for any space-constructible function f(n) and any g(n) that grows strictly more slowly than f(n), there exist languages decidable using f(n) space that cannot be decided using only g(n) space, for both deterministic and nondeterministic machines. It confirms that giving a computer more memory strictly increases what it can compute, so the complexity classes defined by space bounds form a genuine, infinite hierarchy rather than collapsing together, in analogy with the time hierarchy theorems for running time.