Motivation
The preceding note gives a deterministic reachability algorithm that remembers only the endpoints and a proposed midpoint at each recursive level. Its memory use is for a graph with vertices. To simulate a machine using space , we would like to apply that algorithm to its configuration graph, which has roughly vertices. Substituting suggests an simulation.
That substitution is a good prediction, but it is not yet a proof. Writing down the configuration graph could itself require exponential space. We must show that vertex names, midpoint enumeration and adjacency tests can all be handled without constructing the graph. We must also explain how the simulator learns the space limit, why the recursion terminates, and why it finds every accepting computation. These implementation details are the substance of the general theorem.
Definitions and machine conventions
All logarithms are binary. Let denote the input length, including the possibility . Machines have a two-way read-only input between endmarkers and a fixed finite number of work tapes. Their states, alphabets and number of tapes are constants independent of . Work space counts visited work-tape cells; input cells are not charged. Using one work tape changes the bounds below by at most a constant factor, so we describe configurations with one one-sided work tape.
Definition 3.2.1
(Space classes and an effective space limit)
and contain the languages decided by deterministic and nondeterministic machines, respectively, using work space. A nondeterministic decider halts on every branch; it accepts exactly when at least one branch accepts. We use the following convenient space-constructibility hypothesis: is integer valued, , and a deterministic procedure given can compute in binary and delimit a work region of cells using space.
This explicit formulation is sufficient for the standard space-constructible version of Savitch's theorem. Common bounds such as , its square and positive integer powers of satisfy it. The simulator can run the bound procedure on a virtual unary input: it stores a head position and answers whether that position is within . This costs extra bits, already within . No unary copy of the input is necessary.
Fix a machine deciding a language in . Choose a constant integer large enough that work cells suffice for every branch. A configuration contains the state, the input-head position, the work-head position and all work symbols. The description includes blank cells, so each field has a predetermined length once and are known. If is the state set and the work alphabet, then there are at most
such tuples. A tuple can be encoded using
bits, up to a fixed number of delimiter bits. Every term is : in particular and .
The graph that is never stored
Choose a common label length large enough to encode every tuple and one extra target . One explicit convention prefixes each tuple with a , uses a label starting with for , and treats all other -bit labels as invalid. Regard all labels as vertices. Invalid labels are isolated. Add an edge for each legal one-step transition of within the -cell window, and add whenever is an accepting configuration. Let have no outgoing edges. The initial configuration has label .
Proposition 3.2.2
(Implicit configuration graph)
The edge predicate for this graph can be evaluated in work space. Moreover, accepts if and only if is reachable from .
Proof
(Proof)
Given two labels, first check whether their fields encode configurations or the designated target. For a configuration-to-configuration edge, consult the fixed transition table. Locate the input symbol specified by the first label's input-head field by scanning the actual input. Check the changed state, the permitted head movements and the written symbol; compare all other work symbols to ensure they are unchanged. A constant number of labels and scan counters uses space. Testing an accepting-configuration-to-target edge is even simpler. Reject all other proposed edges, including moves leaving the retained work region.
Every accepting computation gives a walk from through legal configurations to an accepting configuration and then to . Conversely, a walk reaching must enter it from an accepting configuration. Starting at the real initial configuration, induction along the preceding edges shows that every visited configuration belongs to a legal computation of . Invalid tuples cannot introduce a false accepting walk because they have no incident edges. Finally, the actual space bound ensures that omitting transitions outside the window removes no computation from .
We count all labels rather than trying to recognize which configurations are reachable. Determining reachability is precisely the problem we are solving. Syntactic validity is easy to test; reachability need not be. This separation also avoids a circular definition of the graph.
The theorem and its proof
Theorem 3.2.3
(Savitch's theorem)
Under the space-constructibility and lower-bound assumptions above,
The simulator is deterministic and halts on every input.
Proof
(Proof by bounded midpoint search)
For labels and an integer , let mean that the implicit graph has a walk from to of at most edges. At level zero, return true exactly when or the edge predicate holds. At positive levels, enumerate every -bit label and return true if both and hold for some . If no label works, return false.
We prove correctness by induction on . The base case includes precisely walks of length zero or one. Concatenating two walks of length at most gives a walk of length at most . Conversely, if a walk has length , choose its vertex after edges. Its two pieces have lengths and , each at most when . The empty walk uses . The induction hypothesis therefore proves the recurrence in both directions.
Any reachable vertex in a graph of vertices has a simple path from the source with at most edges: remove portions between repeated vertices. Thus is true exactly when accepts. This path bound applies to the graph even if the graph has cycles.
It remains to count simultaneous storage. A recursive frame retains , the current candidate , the level , and a constant number of control flags. The labels require bits, the level requires bits, and the whole frame uses . The enumeration counter holds an -bit string; after processing the all-ones string it sets an end flag, so it never needs to store all labels. Levels run from down to zero, giving at most live frames. The two recursive calls for a candidate run sequentially; the first call returns and its temporary frames are discarded before the second begins. A single returned Boolean is enough to decide whether the second is needed. Hence the stack uses space. The bound computation and the adjacency-test scratch space use additional space, for a total of .
Each call has finitely many candidates and calls only smaller levels. Induction on the level shows every call halts. The initial bound computation also halts by hypothesis, completing the deterministic decision procedure.
Proof X-ray
What each part of the Savitch proof is responsible for
The proof has three ingredients that are easy to conflate. The recurrence is a statement about walks only: splitting a walk of length at most at its middle vertex gives halves of length at most , and the case handles walks shorter than the bound. The starting level comes from the simple-path argument, because the graph has labels; this is the only place where cycles in the graph matter. The space bound comes from somewhere else: the two recursive calls run one after the other, so the memory of the first is released before the second starts, and the stack holds at most frames of bits. Keeping the results of finished calls, or running the two calls side by side, would lose the bound. The machine enters only through the edge predicate, which is computable in space.
The recursion may revisit the same question many times. Its call tree has branching at most and depth , giving at most calls. Scanning the input and comparing labels adds a polynomial factor in , absorbed into . The halting deterministic procedure that computes the space limit has only configurations, so its time is absorbed as well. This is an upper bound on this simulation's time, not a time lower bound for the language. Memoizing every answer would change the space calculation substantially.
Concept lensStructural
The stack is one path in a call tree
View the recursion as a tree of subproblems of depth : a node asking tries the midpoints one at a time, and each try has two children at level . A deterministic run visits the nodes depth-first. At any moment only the nodes on one root-to-current-node path are live, so the memory is the path length times the frame size , however many nodes the whole tree contains.
Worked examples
Worked example 3.2.4
(From logarithmic to square-logarithmic space)
Suppose uses at most cells over a fixed alphabet. Its configuration count is polynomial in , its labels have length , and the recursion has live levels of that width. The theorem gives deterministic space . It does not give : multiplying frame width by depth is essential. This explains why Savitch's theorem alone does not prove .
Worked example 3.2.5
(Polynomial space remains polynomial)
If a nondeterministic decider uses space, the construction uses deterministic space. The exponent changes, but the bound remains polynomial. Define and similarly define using deterministic machines. Savitch gives , and viewing a deterministic machine as a nondeterministic machine with one choice gives the reverse inclusion. Thus . No claim that cubic space equals sixth-power space follows: taking the union over all polynomial bounds is what permits the class equality.
Worked example 3.2.6
(A short path with an inexact midpoint)
Let the only edges be , , . The query permits four edges, but its witness has three. Taking splits the witness into lengths one and two, so both level-one calls succeed. Requiring each half to have exactly two edges would reject this graph: there is no four-edge walk from to . The words “at most” in the recurrence and the equality case in the base case accommodate short paths without adding self-loops to the graph.
Simulating a reduction's output tape
There is a second storage issue in the previous note: a logarithmic-space reduction may produce a polynomial-size graph. Composing the reduction with a small-space graph algorithm must not keep that entire output in memory.
Proposition 3.2.7
(On-demand output simulation)
Suppose a deterministic logarithmic-space transducer halts, has polynomially bounded output length, and uses a write-only output tape whose previous contents do not affect transitions. If a decider for uses space on inputs of length , then is decidable in space.
Proof
(Proof)
First run while counting its emitted symbols to compute . Since is polynomially bounded in , the counter uses bits. Simulate the decider for , retaining its work tapes and the position of its virtual input head. On a request to read output position , restart from its initial state, count emitted symbols, and return the th symbol when it is produced. Positions outside return the appropriate input endmarker. The transducer's restart uses scratch space, while the suspended decider uses space. The spaces add because we retain one state while computing the requested symbol. Every restart halts, and the simulated decider halts. It receives exactly the input , proving correctness and the claimed bound.
For example, if is an adjacency matrix, a query for one entry is answered by replaying the reduction until it emits that entry. Recomputing a long prefix is expensive in time but cheap in reusable memory. Combining this proposition with the earlier NL-completeness reduction and deterministic reachability proof yields independently of the general theorem.
Common mistakes and limits
Common mistake
(Cycles in a general reachability graph)
On a graph with edges , , and , there are accepting walks that loop many times before reaching . A later choice can leave the cycle, so repetition does not force every continuation to loop forever. However, repeatedly choosing the cycle gives an infinite walk. Thus this example cannot be the reachable part of the configuration graph of a decider whose every branch halts. Cycle removal proves a short accepting witness exists even for general graphs; it does not bound the length of every walk in those graphs. The search proof applies to that broader setting as well.
The lower bound pays for the input-head field. Without it, the displayed encoding has size , and this proof does not establish an bound. Nor may one silently choose a noncomputable space budget and assume the simulator can delimit it: the constructibility hypothesis supplies that procedure. These observations delimit this proof; they do not claim the theorem's hypotheses are logically necessary in every possible formulation.
Counterexample mode
Every midpoint instead of some midpoint
A tempting variant replaces "some midpoint works" by "every midpoint works", hoping to simulate universal choices as well. Take vertices , and an isolated vertex , with the single edge . Then should hold, since is reachable in one edge. For the midpoint both and hold, and the same is true for . For , however, fails because and there is no edge . The universal rule therefore answers false although is reachable. The recurrence is correct only with existential choice; alternating machines, which have both kinds of choice, need a separate analysis.
Exercises
Quick check
(Why is it safe for the implicit graph to contain labels for configurations unreachable from ? Why would arbitrarily adding edges out of reachable configurations be unsafe?)
Solution · Answer
Every edge out of a reachable configuration is checked against 's transition relation, so induction preserves legal reachability. Unreachable but syntactically valid configurations cause no false positive. Arbitrary added edges could connect the reachable region to such a configuration and then to an accepting configuration, violating that invariant. For instance, adding a start-to-accepting edge would immediately change rejection into acceptance.
Quick check
(A machine has states, a binary work alphabet including the blank, input length , and a -cell work window. Compute the tuple-count bound and give a sufficient recursion level after adding the target.)
Solution · Answer
The bound is . Adding a target gives at most vertices, so a simple path has at most edges and level suffices. The explicit encoding of the proof uses bits and level , a larger but also sufficient choice.
Quick check
(Show explicitly why a recursive implementation that retains every completed subproblem can lose the bound.)
Solution · Answer
The graph can have vertices, hence endpoint pairs at a single level. A table for every pair can therefore require exponentially many entries. Savitch's stack retains only live frames and deliberately recomputes finished questions. The table size is a possible cost of that implementation, not a lower bound on every algorithm.
Quick check
(Apply the theorem to . State the resulting deterministic space bound and the given simulation's time upper bound.)
Solution · Answer
The deterministic space bound is . The search-time bound is , obtained from . The input-scanning factors are absorbed in this bound.
Quick check
(Does imply or ? Explain exactly what the proof provides.)
Solution · Answer
Neither equality follows from this argument. Squaring a polynomial bound keeps it inside the union of polynomial-space bounds, while squaring a logarithmic bound produces a larger stated bound. The construction also gives no polynomial-time simulation of nondeterminism.
Quick check
(Suppose a reduction has output length at most . How much memory is required for its virtual input head? Why does restarting the reduction preserve the symbol under that head?)
Solution · Answer
The position is at most plus endmarkers, so it needs bits. A deterministic transducer restarted on the same fixed input emits the same sequence. Counting to the saved position therefore returns the same symbol each time, without preserving its earlier output.
The central accounting is now explicit: one configuration costs bits, the search has live levels, and sequential subcalls reuse their temporary memory. The next questions in space complexity need additional ideas, including complement closure for nondeterministic space and complete problems for polynomial space.