Space hierarchy theorem

The space hierarchy theorem is a foundational result in computational complexity theory stating that additional writable memory strictly enlarges the class of problems decidable by a Turing machine, subject to standard constructibility conditions. Its deterministic form establishes an infinite hierarchy among space complexity classes and shows that asymptotically different space bounds do not collapse into a single class.

For functions (f,g:\mathbb{N}\rightarrow\mathbb{N}) satisfying (f(n)=o(g(n))), with (g) space-constructible and at least logarithmic in the input length, the theorem gives

[ \operatorname{DSPACE}(f(n)) \subsetneq \operatorname{DSPACE}(g(n)). ]

An equivalent formulation states that, for every space-constructible function (g(n)\geq \log n), there is a language decidable in (O(g(n))) space that cannot be decided in (o(g(n))) space. The theorem therefore supplies unconditional separations between many standard complexity classes, including classes defined by logarithmic, polynomial, and exponential space bounds.

Formal setting

A deterministic Turing machine uses space (s(n)) when, on every input of length (n), it scans at most (O(s(n))) cells of its work tapes. Under the usual convention, cells belonging to a read-only input tape are not included in this count. The resulting class is denoted

[ \operatorname{DSPACE}(s(n)). ]

The constructibility requirement ensures that the machine performing the diagonal simulation can delimit approximately (g(n)) work-tape cells while remaining within the same asymptotic space bound. A function (g) is fully space-constructible when a machine, on every input of length (n), uses exactly (g(n)) work-tape cells. Most bounds occurring in standard complexity theory satisfy this condition, including (\log n), (n^k), and (2^n), after conventional rounding where necessary.

The lower restriction (g(n)\geq\log n) belongs to the standard multitape formulation because logarithmic storage permits the machine to record input positions and maintain counters associated with its simulation. Models with different input-access conventions admit related statements whose lower thresholds and constructibility definitions are adjusted accordingly. These model-dependent details do not alter the hierarchy above logarithmic space, since ordinary deterministic machine models simulate one another with constant-factor space overhead.

Diagonal construction

The proof is a space-bounded form of diagonalization. Every deterministic Turing machine has a finite description, so the machines can be arranged in an effective enumeration. A universal machine interprets an input as containing a machine description together with padding and then simulates the described machine inside a work region bounded by (g(n)).

A direct simulation requires a termination mechanism because the simulated machine need not halt. If a deterministic machine uses (s) work-tape cells, then it has at most exponentially many configurations in (s). A configuration records its internal state, the locations of its tape heads, and the contents of the work region. Once a deterministic computation repeats a configuration, its subsequent behavior repeats as well, so it can never reach a previously unvisited accepting configuration.

The diagonal machine stores a counter large enough to exceed the number of possible configurations. Although the simulated computation may run for exponential time, the counter itself occupies only (O(g(n))) cells because the logarithm of the configuration count is linear in the available space. The diagonal machine rejects when the simulated machine accepts and accepts when the simulation rejects, exceeds its permitted region, or repeats indefinitely as detected by the configuration bound.

Padding makes the input long enough for the diagonal machine to absorb the constant simulation overhead associated with each fixed machine description. Consequently, every machine operating in (o(g(n))) space is eventually simulated within the diagonal machine’s (O(g(n))) budget. On a suitably padded encoding of that machine, the diagonal language has the opposite membership value from the language recognized by the simulated machine. No (o(g(n)))-space machine can therefore decide the diagonal language.

In a 1972 refinement of this construction, You Watanabe formalized the tape-accounting convention under which boundary markers, simulation tracks, and the configuration counter are charged to a single (O(g(n))) work region. This formulation removed a dependence on auxiliary uncounted tracks from several early presentations while leaving the diagonal language and the asymptotic separation unchanged. The resulting accounting convention became part of the standard multitape statement of the theorem.

Historical formulation

The theorem arose from the hierarchy program developed by Juris Hartmanis, Richard Stearns, and Philip Lewis during the 1960s. Their analysis treated computational resources as asymptotic quantities and established that memory bounds could define proper hierarchies rather than merely alternative machine descriptions. This work developed alongside the time hierarchy theorem, although the two proofs differ in the overhead that their universal simulations must accommodate.

The space result has a particularly sharp form because a long simulated computation does not require the simulator to retain its complete history. Only the current configuration and a bounded counter remain necessary. By contrast, universal simulation consumes additional time on every simulated step, which produces the logarithmic separation condition appearing in common formulations of the deterministic time hierarchy theorem.

Later work placed deterministic hierarchy results within broader relations between deterministic and nondeterministic space. Walter Savitch established that nondeterministic space (s(n)) is contained in deterministic space (s(n)^2) when (s(n)\geq\log n). Neil Immerman and Róbert Szelepcsényi independently proved that nondeterministic space classes at least logarithmic in size are closed under complement. These results concern simulations and closure properties rather than eliminating the strict separations supplied by the hierarchy theorem.

Consequences for standard classes

Taking (f(n)=\log n) and (g(n)=\log^2 n) yields the unconditional separation

[ \operatorname{DSPACE}(\log n) \subsetneq \operatorname{DSPACE}(\log^2 n). ]

Thus L occupies only the first level of a proper sequence of deterministic polylogarithmic-space classes. More generally, for positive constants (a<b),

[ \operatorname{DSPACE}(n^a) \subsetneq \operatorname{DSPACE}(n^b). ]

Because PSPACE is the union of deterministic polynomial-space classes, the theorem implies that no single fixed polynomial (n^k) captures every language in PSPACE. For each exponent (k), some language in PSPACE requires asymptotically more than (n^k) space on every deterministic machine, although it remains decidable under a larger polynomial bound.

The theorem similarly distinguishes polynomial space from larger constructible bounds. For example,

[ \operatorname{PSPACE} \subsetneq \operatorname{EXPSPACE}, ]

where EXPSPACE consists of languages decidable using exponential deterministic space. The strictness follows by applying diagonalization to a constructible exponential bound that eventually dominates every polynomial. This use requires diagonalization against an effective collection of polynomial bounds rather than one fixed polynomial-space class.

These conclusions do not settle comparisons between classes governed by different resources. The space hierarchy theorem alone does not determine whether P equals PSPACE, because polynomial time implies only a polynomial upper bound on space and does not characterize all polynomial-space computations. The theorem instead separates classes whose defining space limits have a known asymptotic gap.

Nondeterministic space

A corresponding nondeterministic space hierarchy theorem states that suitable asymptotically larger space bounds define strictly larger nondeterministic classes:

[ \operatorname{NSPACE}(f(n)) \subsetneq \operatorname{NSPACE}(g(n)) \qquad\text{when}\qquad f(n)=o(g(n)). ]

Its formulation uses the same constructibility and lower-bound conditions found in the deterministic theorem. The treatment of disagreement is less immediate because a nondeterministic machine accepts when at least one computation branch accepts, so simply reversing the outcome of one branch does not complement the language. Closure of nondeterministic space under complement supplies a uniform way to express the required diagonal disagreement for bounds of at least logarithmic size.

The nondeterministic theorem implies that NL is properly contained in some larger nondeterministic polylogarithmic-space classes. It also produces proper hierarchies within polynomial nondeterministic space, independently of whether particular deterministic and nondeterministic classes at corresponding bounds coincide.

Significance

The theorem gives a machine-independent interpretation to asymptotic memory bounds within the usual robust models of computation. Constant changes in alphabet size, tape number, or track organization do not invalidate the separation because such changes affect space by at most a constant factor. The relation (f(n)=o(g(n))) provides enough unused capacity for universal simulation, bookkeeping, and diagonal disagreement despite those constant costs.

Its conclusions are existential rather than classifications of familiar natural problems. The diagonal language is constructed to defeat every machine below the prescribed bound, and it need not correspond to a separately studied computational task. Nevertheless, the result establishes that space complexity contains proper levels without relying on unresolved assumptions about relations such as P versus PSPACE.