Motivation
Savitch's theorem tells us how nondeterministic space can be simulated deterministically, but it does not say whether giving a deterministic machine more memory makes it more powerful. The space hierarchy theorem answers that question under a constructibility hypothesis. Its diagonal machine simulates a candidate within a carefully chosen intermediate memory budget, waits long enough to detect repeated configurations, and then disagrees with it.
The key comparison is asymptotic. A program has a fixed description and a fixed simulation constant, while the ratio between two space bounds can grow without bound. Encoding and counting configurations matter: a simulation that waits for an arbitrary machine to halt would not itself be a decider.
Definition 3.7.1
(Space bound and space constructibility)
We use deterministic machines with a read-only input tape and a bounded work tape. The work-space bound counts visited work cells, not the read-only input. A function is space constructible here if a deterministic machine can, on inputs of length , construct and mark exactly work cells using space. We assume for sufficiently large , so a machine can store an input-head position and elementary counters. Changing finitely many values of a bound does not affect the resulting asymptotic space class.
Why a space bound gives a clock
Theorem 3.7.2
(Configuration bound)
Fix a deterministic machine with a finite work alphabet. On an input of length , if uses at most work cells, its number of possible configurations is at most for a constant depending on but not on or . If a computation repeats a configuration, it never subsequently halts.
Proof
(Counting configurations and the pigeonhole step)
A configuration records the finite control state, the contents of the visited work window, the work-head position and the input-head position. A work alphabet of size gives at most possible window contents; the head positions contribute factors at most and , and the state set is fixed. For suitable , the product is at most the displayed power of two, including small after increasing .
A deterministic next-step rule gives the same continuation from equal configurations. If a configuration repeats before halting, the segment between its occurrences repeats forever, so the computation cannot later halt. Thus a simulation with a valid bound on the number of configurations can safely declare nonhalting after more than that many steps.
Worked example 3.7.3
(A small finite state space)
Suppose a machine has two control states, a binary work tape restricted to three cells, four possible work-head positions and six input-head positions. At most configurations are possible. A deterministic computation that has not halted after observing 385 configurations has repeated one. This finite example illustrates the pigeonhole argument; the hierarchy proof needs the general bound as input length grows, with the machine description treated consistently throughout the simulation.
Common mistake
(A large clock does not require a large tape)
A counter that runs up to uses bits, although counting to that value can take exponential time. The hierarchy argument is a space proof, not a polynomial-time simulation. Its large clock is compatible with the claimed memory bound.
Concept lensStructural
Configurations form a graph with one exit each
Take the configurations of a deterministic machine on a fixed input as vertices, with an edge from each configuration to its successor. Every vertex has at most one outgoing edge, and a computation is the walk from the start vertex. The walk halts exactly when it reaches a halting vertex; if it revisits a vertex it is on a cycle and never halts. A clock therefore only has to count up to the number of vertices.
Simulating a described machine
We use a standard universal interpreter for a fixed finite machine encoding. Its transition table is read from the read-only input rather than copied wholesale to the work tape. For a fixed described machine , simulating of its work cells needs at most interpreter work cells, where is a constant depending on and its alphabet. The interpreter can track the described machine's state and head positions, scan its description when it needs a transition, and count simulated work cells. The extra scans may cost time; no time bound is claimed. The usual finite-alphabet encoding and universal simulation are background assumptions here.
For the diagonal construction we also need a uniform configuration clock for the interpreter itself. We restrict the encoded machine description to at most input bits, and cap the interpreter's work window at cells. The interpreter is one fixed machine, so its own configurations have at most possibilities for one fixed constant . The description is already part of the fixed input and is not another changing component of its configuration. The clock has bits.
Worked example 3.7.4
(Fixed program, growing padding)
An encoding can consist of a self-delimiting description of followed by zeros. For every fixed , the description length is a constant. By padding sufficiently, it becomes at most , while the simulated input remains the entire padded string. Thus restricting the description length does not exclude any fixed candidate machine from all sufficiently long diagonal inputs.
Choosing a budget between two bounds
Let be space-constructible functions, eventually at least , with . Define
Then and . The ceiling changes neither limit. In particular eventually. A diagonal machine can calculate a sufficiently accurate integer using work space: construct the two bounds, represent their numerical values in binary, multiply and take an integer square root. This bound includes the work needed to construct for sufficiently large , since . For finitely many short inputs the machine may use any fixed fallback behavior.
Theorem 3.7.5
(Deterministic space hierarchy)
Under the stated hypotheses,
Proof
(Diagonalizing against every fixed small-space machine)
On an input of length , the diagonal machine first attempts to parse a valid self-delimiting deterministic-machine description of length at most . If the input has no such description, it rejects. Otherwise it computes , allocates an interpreter work window of cells, and simulates the described machine on the same entire input . If the interpreter attempts to leave its window, the diagonal machine rejects. It also maintains the uniform configuration clock described above. If the clock expires before the simulation halts, it rejects. If the simulated machine accepts, the diagonal machine rejects; if it rejects, the diagonal machine accepts.
The construction always halts: a window violation, a simulated halt or the finite clock ends the run. Constructing costs space; the simulation and its clock cost space. Thus the resulting language is in .
Suppose for contradiction that a fixed decider decides using at most work cells for all large . Take padded inputs that encode and whose lengths tend to infinity. Eventually the description-length restriction is met. The universal interpreter's space for this fixed is at most , which is less than for all sufficiently large such lengths because and . Therefore the window does not overflow. The simulated decider halts, and the clock is long enough: otherwise a configuration of the bounded deterministic interpreter would repeat and the simulation could never subsequently halt. The diagonal machine then outputs the opposite of , contradicting the assumption that decides . Hence .
The ordinary inclusion follows since eventually. The strictness proof needs a single fixed candidate machine when absorbing its simulation constant; it does not assume one constant works equally for every encoded program.
Proof X-ray
Where each hypothesis enters the diagonal argument
The argument has two halves with different quantifiers. The upper bound holds for every input: the machine halts and uses space, which needs constructibility (to build ), (so that ) and the uniform clock of one fixed interpreter with one constant . The lower bound concerns only a single candidate , whose constant is fixed before grows. The non-obvious move is the padding: the diagonal machine reads the description of from its input, and appending zeros makes a fixed occur on infinitely many inputs, so the description-length cap excludes no candidate. Hypothesis enters the lower bound exactly once, through , which makes the window eventually exceed . If this step fails: is only about , the window can overflow, the diagonal machine then rejects without disagreeing with , and no contradiction appears.
Worked example 3.7.6
(Logarithmic versus squared-logarithmic space)
Take and . Both are space constructible and . The theorem gives a language decidable in space but not in space. The proof is existential through a diagonal decider; it does not identify a familiar complete problem with this property.
Counterexample mode
A constant factor never separates space classes
A tempting claim is that the hierarchy still gives when , since the larger bound allows ten times as much memory. Take and . Then does not tend to zero, so the hypothesis fails, and so does the conclusion. If a machine decides a language using at most work cells, build whose work alphabet consists of blocks of ten symbols of , with the position inside a block kept in the finite control. Then simulates step by step, uses at most block cells and decides the same language. Hence even for exact bounds, and a strict separation needs the little-o gap .
A consequence and a closer look at the clock
Corollary 3.7.7
(A strict containment inside PSPACE)
.
Proof
(The squared-logarithm witness)
The squared-logarithm example supplies a language in that is not in . Since is bounded above by a polynomial in , this language belongs to PSPACE. Every logarithmic-space machine also uses polynomial space, so ; the constructed language makes the containment strict. This conclusion uses the deterministic space hierarchy and does not settle the relation between P and PSPACE.
Worked example 3.7.8
(Space used by an exponential clock)
Suppose the bounded interpreter has at most possible configurations. Counting from zero to takes 101 binary bits, plus a constant amount of control space. A counter of that size can be maintained alongside the interpreter window; its potentially enormous running time is allowed in a space-class argument. If a simulation of a decider stays inside its window, it must halt before a configuration repeats, so this clock cannot incorrectly time it out.
The clock bounds configurations of the bounded interpreter, not merely configurations of the simulated machine with its program-dependent alphabet. This choice produces one uniform constant in the diagonal construction. Conversely, to show that any fixed small-space candidate fits the interpreter window, the proof may use a constant depending on that one candidate. Mixing those two quantifiers would leave the diagonal decider without a uniform bound.
What the theorem does and does not compare
The theorem is about deterministic space classes and languages. It neither says that every language in the larger class is hard for the smaller class nor proves a separation such as P versus PSPACE. It produces one language in the difference. It also does not establish the nondeterministic space hierarchy, which needs a separate argument.
Space constructibility is not decorative: the diagonal machine has to allocate and monitor a budget derived from the named functions. Without some effective access to those bounds, the construction described above is not justified. The hypothesis pays for indexing the read-only input and for the simulator's counters; sublogarithmic models require additional care.
A nondeterministic hierarchy with the same gap holds, but the diagonal machine must now complement an answer.
A natural next question
Does the same gap separate nondeterministic space?
A nondeterministic hierarchy with the same gap holds, but the diagonal machine must now complement an answer.
A nondeterministic space hierarchy with the same little-o gap is also true. The deterministic proof used above flips the answer of the simulated machine, which for a nondeterministic machine requires deciding the complement of its language within the available space. That is why the nondeterministic case needs a separate argument, and the complement result for nondeterministic space is the relevant tool.
Practice and solutions
Quick check
(Why can a clock of exponential length fit in linear space in its exponent?)
Count the bits of the largest number the clock reaches.
Solution · Answer
A binary counter up to needs only bits, even though it may execute exponentially many increments.
Quick check
(What goes wrong if a deterministic configuration repeats before the machine halts?)
Compare the continuation after each occurrence.
Solution · Answer
Determinism makes the same future repeat, so the machine loops forever and cannot later halt.
Quick check
(Why does the diagonal machine simulate the described program on the entire padded input rather than only on its description?)
Which input must the candidate decide?
Solution · Answer
The purported candidate decides the diagonal language on the full input. Disagreement on that same input is what yields the contradiction.
Quick check
(Why is eventually larger than every fixed multiple of ?)
Bound from below by one square root.
Solution · Answer
Since and , the ratio tends to infinity.
Quick check
(Where is the space-constructibility hypothesis used?)
Ask what the diagonal machine must compute before simulating.
Solution · Answer
It lets the diagonal algorithm construct and monitor its input-length-dependent memory budget within the larger space allowance.
Quick check
(Does the proof imply is strictly smaller than ?)
Check the little-o hypothesis for a constant factor.
Solution · Answer
No. The required little-o relation fails for a constant factor, and the block-packing argument shows that the two classes coincide.
Quick check
(Does the theorem prove P differs from PSPACE?)
What exactly is separated?
Solution · Answer
No. The theorem separates suitable deterministic space bounds; it does not compare all polynomial-time languages with PSPACE.
Quick check
(Why does follow even though the hierarchy proof does not identify a familiar natural language in the difference?)
Is a witness required to be a standard problem?
Solution · Answer
It constructs a particular diagonal language in outside . The larger class is contained in PSPACE, so that constructed language witnesses strictness even if we do not recognize it as a standard graph problem.