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.
Facts
StatementFor all space-constructible functions f(n) and all g(n) in o(f(n)), SPACE(g(n)) is a proper subset of SPACE(f(n)). 1 Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Space hierarchy theorem, Wikipedia
Sources
1. Space hierarchy theorem, Wikipedia
Lead paragraph
The deterministic and nondeterministic space hierarchy theorems state that for all space-constructible functions f(n) and all g(n) ∈ o(f(n)), SPACE(g(n)) ⊊ SPACE(f(n))
In Branch: Computational Complexity Theory, Lead sentence
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nond
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.