Configuration Graphs and Savitch's Reachability Argument

A machine running in time $t$ can be in at most $t$ different configurations, because each step moves it to a new one. That simple observation turns any bounded computation into a graph search: build the graph whose vertices are configurations and whose edges are single steps, and ask whether the start vertex reaches an accepting vertex. The construction is mechanical, and it converts questions about machines into questions about reachability that can then be answered by algorithms with their own resource bounds. Savitch’s theorem is the sharpest result obtained this way, and it depends on a property of reachability that is easy to miss: the problem is recursive in a way that the underlying path is not.

The size of the graph

A configuration of a Turing machine consists of the state, the contents of the non-blank portion of the tape, and the head position. For a machine with $s$ states, tape alphabet of size $|\Gamma|$, and space bound $f(n)$, the number of configurations is at most

$$s \cdot f(n) \cdot |\Gamma|^{f(n)} \cdot f(n),$$

where the two factors of $f(n)$ account for the head position and the length of the used tape, and the exponential factor accounts for the tape contents. Taking logs, the number of configurations is $O(f(n))$ bits to describe, so the graph has exponentially many vertices in its description length but only $2^{O(f(n))}$ vertices in absolute terms.

For a machine running in time $t$, the reachable configurations are at most $t + 1$, so the relevant subgraph is small. For a machine running in space $f(n)$, the whole graph can be large even if the machine halts quickly, and the distinction between “the graph exists” and “the graph is explored” is what makes space complexity different from time complexity.

The graph is not usually built. Its vertices are configurations, which are exponentially long strings; materializing them would use exponential space. Every algorithm in this area works with implicit graphs, where a vertex is represented by the configuration that generates it and edges are computed by simulating one step. This is the same distinction as between an explicit adjacency list and a function that enumerates neighbours, and it is what allows a space-bounded algorithm to reason about an exponentially large graph without storing it.

Reachability in small space

The straightforward algorithm is breadth-first search from the start vertex, which needs to remember the visited set. On an implicit graph with $2^{O(f(n))}$ vertices that costs $2^{O(f(n))}$ space, which is exponential in the space bound and therefore useless for proving anything about space classes.

The alternative is a recursive divide-and-conquer on path length. Define $\mathrm{REACH}(u, v, k)$ to mean “there is a path from $u$ to $v$ of length at most $k$”. The base case $k = 1$ is a single edge, checked by simulating one step. The recursive case halves the length: there is a path of length at most $k$ from $u$ to $v$ exactly when there exists a vertex $w$ with a path of length at most $\lceil k/2 \rceil$ from $u$ to $w$ and a path of length at most $\lfloor k/2 \rfloor$ from $w$ to $v$.

def reach(adj, u, v, k):
    # adj maps each vertex to its successor list; k is a power of two
    if k == 1:
        return v in adj[u]
    for w in adj:
        if reach(adj, u, w, k // 2) and reach(adj, w, v, k // 2):
            return True
    return False

The loop over intermediate vertices is the source of the time cost, and the recursion is the source of the space cost. Both are worth counting separately. On a configuration graph the adjacency map is never materialized; v in adj[u] is replaced by simulating one machine step from the configuration u, and the loop over vertices is replaced by enumerating configurations with a counter.

Space: each level of recursion holds the current vertex pair and the loop counter, which is $O(f(n))$ bits for a configuration plus $O(\log k)$ bits for the counter. The recursion depth is $\log k$, since $k$ halves at each level. So the total space is $O(f(n) \log k)$, and with $k$ bounded by the number of configurations, $2^{O(f(n))}$, the logarithm is $O(f(n))$, giving $O(f(n)^2)$ space.

Time: at each level, the loop tries every possible intermediate vertex, of which there are $2^{O(f(n))}$. The recursion tree therefore has branching factor $2^{O(f(n))}$ and depth $O(f(n))$, so the time is $2^{O(f(n) \cdot f(n))}$, double-exponential in $f(n)$ and useless as an algorithm. The theorem is a statement about space, and it is proved by an algorithm that is deliberately allowed to be slow.

The composition that gives the square

The key step is the space recurrence. If a problem is solvable by a nondeterministic machine in space $f(n)$, then it is solvable by a deterministic machine in space $O(f(n)^2)$. The proof composes three observations.

First, the nondeterministic computation accepts $x$ exactly when the start configuration reaches an accepting configuration in the configuration graph of the machine on $x$. This is a deterministic reduction: given $x$, the graph is determined, and the question is a reachability question about it.

Second, reachability in an implicit graph with $N$ vertices is decidable in space $O(\log N)$ by the recursive algorithm above, provided the vertices can be enumerated and edges computed in space $O(\log N)$. Here $N = 2^{O(f(n))}$, so $\log N = O(f(n))$, and the recursive algorithm uses $O(f(n) \log N) = O(f(n)^2)$ space. The enumeration of intermediate vertices is done by a counter of $\log N$ bits, which is $O(f(n))$ bits.

Third, the deterministic machine implementing the recursion must be able to store a configuration, which takes $O(f(n))$ bits, and must be able to simulate one step of the nondeterministic machine, which it can do deterministically because a nondeterministic step is a relation and the deterministic simulation checks each successor in turn. Checking each successor in turn costs time but not space.

Combining them: the deterministic machine uses $O(f(n)^2)$ space. The quadratic comes from the $O(\log N)$ counter multiplied by the $O(\log N)$ recursion depth, with $\log N = O(f(n))$.

The corollary that matters is $\mathrm{NPSPACE} = \mathrm{PSPACE}$, obtained by taking $f(n)$ to be a polynomial: if a nondeterministic machine uses $n^k$ space, the deterministic machine uses $n^{2k}$ space, which is still polynomial. So nondeterminism buys nothing for polynomial space, in sharp contrast to the time case, where the analogous statement $\mathrm{NP} = \mathrm{P}$ is open and widely believed false.

Why the argument does not transfer to time

The same recursive decomposition applied to time would give a deterministic simulation of nondeterministic time with only a quadratic slowdown, which would prove P equals NP. It does not, because the space accounting and the time accounting behave differently under the recursion.

In the space version, the recursion is sequential: the two recursive calls are made one after the other, and the first call’s space is released before the second begins. The peak space is therefore the depth times the per-level space, not the branching factor times the depth. That is what makes the space bound additive in the depth.

In a time version, the same sequential evaluation would re-run the first call for every choice of intermediate vertex, and the total time would multiply by the number of choices at every level. The time cost is the size of the recursion tree, not its depth. This is the fundamental asymmetry: space composes additively along a path, time composes multiplicatively across a tree.

There is a second reason the argument does not transfer. The number of configurations reachable in time $t$ is at most $t$, so $\log N = O(\log t)$, and the recursive algorithm would use $O(\log^2 t)$ space, which is a genuine theorem about reachability in small space, but it says nothing about whether the nondeterministic machine’s computation can be simulated fast. The algorithm’s running time is exponential in $t$, so it establishes a space bound and no time bound.

Consequences for the space hierarchy

Savitch’s theorem places nondeterministic space between deterministic space and its square:

$$\mathrm{DSPACE}(f(n)) \subseteq \mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2).$$

For the smallest space bounds the picture is unusually delicate. Reachability in a directed graph is complete for NL, and whether it has a deterministic logarithmic-space algorithm is open. This is the question of whether L equals NL. What the space hierarchy theorem does give is a strict inclusion one level up: L is strictly contained in DSPACE(log² n), since log n is asymptotically smaller than log² n by a constructible factor. Savitch’s theorem closes the gap from the other side by placing NL inside DSPACE(log² n). So the two bounds sandwich NL between L and DSPACE(log² n), and neither inclusion is known to be tight.

The space hierarchy theorem itself is proved by diagonalization, like its time counterpart, and the time hierarchy argument carries over with the resource changed. The difference is that the space hierarchy is finer: the separation between $f$ and $g$ holds whenever $f$ is asymptotically smaller than $g$ by any constructible factor, not just a logarithmic one, because a machine can simulate a smaller-space machine with only a constant-factor space overhead.

Immaterial for the class landscape, but worth stating: $\mathrm{PSPACE}$ contains $\mathrm{NP}$, since a polynomial-time computation uses polynomial space. Whether it contains more is open, and the standard conjecture is that it does, that $\mathrm{NP} \subsetneq \mathrm{PSPACE}$, because quantified boolean formulas with unbounded alternation are PSPACE-complete and are not known to be in NP. The polynomial hierarchy is the structure that would collapse if that conjecture failed.

The configuration graph as a reusable device

The construction generalizes. For any machine model with a finite description of its instantaneous state, the computation is a path in a graph whose vertices are those descriptions, and questions about the computation become questions about the graph. Three consequences follow directly.

Reachability being in NL gives a uniform way to show that a problem is in NL: exhibit a nondeterministic log-space machine whose configurations encode the problem’s state, and observe that the machine accepts exactly when a path exists. This is how directed reachability, 2-SAT, and several other problems are placed in NL.

The undecidability of reachability in some graph classes, and the decidability in others, is a statement about the graph’s structure rather than about the machine. Pushdown automata have configuration graphs whose reachability problem is decidable, which is why context-free language membership is decidable; two-counter machines have configuration graphs whose reachability problem is undecidable, which is why their membership problem is not.

And the size of the graph gives an upper bound on the resources needed to decide the problem by brute force: $2^{O(f(n))}$ vertices means $2^{O(f(n))}$ space for an explicit search, which is the trivial upper bound that Savitch’s theorem improves to $O(f(n)^2)$ for the nondeterministic case. The improvement is the whole content of the theorem, and it comes from the one structural fact that reachability has and path-finding does not: a path of length $k$ can be certified by a midpoint, and the two halves can be checked one after the other.