The preceding space unit defined logarithmic work space and proved directed reachability belongs to NL. Here we prove the complementary hardness statement by producing a configuration graph, then replace nondeterministic guessing by a deterministic midpoint search. The companion Savitch unit proves the general simulation and the reduction-composition lemma used below.
Why directed reachability is NL-complete
Definition 3.4.1
(Logarithmic-space many-one reduction)
A logarithmic-space many-one reduction computes its output on a write-only output tape while using only logarithmic work space. The output can be polynomially long: its cells are not charged to the work-space bound. This distinction is exactly what permits the next construction. We will generate the description of a graph one edge at a time, rather than retaining the graph or the breadth-first search marks in memory.
Theorem 3.4.2
(Directed reachability is NL-complete)
Under logarithmic-space many-one reductions, directed reachability is complete for , for standard explicit encodings of directed graphs.
Proof
(Proof of NL-hardness)
Membership in was proved in the preceding space unit by guessing a path of length at most one less than the number of vertices. For hardness let , and fix a nondeterministic log-space decider for in the standard one-sided work-tape model. The finitely many inputs of length below two can be handled by hard-coded yes- and no-instances of reachability. Its state set and work-tape alphabet are fixed constants. Choose an integer constant so that on every input of length the machine visits at most work cells. On input , define a configuration by a state, input-head position, work-head position, and contents of these cells. There are at most
candidate configurations. The upper bound includes impossible combinations; that causes no problem because only configurations reachable from the true start can affect the answer. Transitions leaving the retained work-tape window are omitted: the space bound ensures no branch from the true start needs one.
Give every candidate a distinct numerical label of bits. Output a graph with these candidates as vertices, together with one fresh sink vertex. There is an arc from to exactly when one transition of on the fixed input changes into . Add an arc from every accepting configuration to the fresh sink. Self-loops may be omitted without changing reachability to the distinct sink, so the output can be a loopless simple digraph. Let the source be the initial configuration and the target be the fresh sink. An accepting computation of is a walk from source to sink. Conversely, every source-to-sink walk follows legal transitions until it reaches an accepting configuration, so it describes an accepting branch. Thus exactly when the output graph has a source-to-sink path.
It remains to justify the resource bound, rather than merely noting that the graph is polynomial in size. Enumerate ordered pairs of candidate labels using two -bit counters. Decode each label into a state, head positions, and a work-tape word of length ; both decoded configurations fit in work space. To test a proposed transition, scan the read-only input to the position specified by the input head and compare the configurations against the fixed transition table. Print the corresponding adjacency-matrix bit on the write-only output tape, and reuse the same cells for the next pair. Candidate and edge counts are polynomial, so this procedure terminates in polynomial time. The initial and accepting configurations are recognized within the same work bound. Hence the graph and designated vertices are produced in logarithmic work space, proving reduces to reachability.
Proof X-ray
What the configuration-graph reduction relies on
The graph includes every syntactically valid tuple, whether or not it occurs in a real computation, and the proof needs only two facts. Soundness is an induction on path length: the source is the true initial configuration and every arc is a legal transition, so every vertex reachable from the source is a configuration that really occurs, and spurious tuples elsewhere cannot lie on a path from the source. Completeness uses the space bound once: every branch from the true start stays within cells, so cutting the window dropped no needed transition. The sink is fresh, so each accepting configuration contributes exactly one new arc, and acceptance of is equivalent to reaching the sink. The resource bound is a separate argument about the producer, not about the graph.
The correctness and the space analysis answer different questions. It is not enough that a graph of polynomial size exists: the reduction must be able to enumerate it with logarithmic work memory. Conversely, a write-only output tape is not a secret reservoir the reduction may later reread; the construction recomputes or re-enumerates information whenever needed. Once NL-hardness is available, the square-logarithmic reachability algorithm below implies using the log-space-reduction composition simulation proved in the companion note, which also proves the stronger general Savitch theorem.
A deterministic square-logarithmic algorithm
In the preceding unit nondeterminism was used to guess a path. We now eliminate it at a quadratic-logarithmic price.
Definition 3.4.3
(Bounded-length reachability)
For vertices and an integer , write for the statement that there is a directed walk from to with at most edges.
Proposition 3.4.4
(Deterministic space for reachability)
Directed reachability on graphs with vertices can be decided by a deterministic algorithm using work space.
Proof
(Proof)
Define to hold exactly when or is an edge. For we claim that holds if and only if there is a vertex with and . If such a exists, concatenating the two walks gives a walk of at most edges. Conversely, take a walk from to with edges and let be its vertex after edges. The first part has edges and the second part has edges, because gives and is an integer. When we have and take .
Let , so . By the simple-path argument of the previous proposition, is reachable from if and only if holds. Evaluate recursively: for inspect the input directly, and for loop over all vertices in order, testing and then , and accept at the first success. Each stack frame stores , , the loop variable , and the level . That is three vertex names of bits each plus bits for the level. The recursion depth is , and the frames of finished subcalls are discarded and reused. The total work space is , plus the pointer needed to read the input.
This is the space-saving mechanism in Savitch's theorem. The recursion reuses the memory for the first half of a walk when it moves to the second half. The price is time: each level makes up to recursive calls, so the number of calls is at most , which is quasi-polynomial rather than polynomial.
Worked example 3.4.5
(The midpoint recursion on a four-vertex path)
Let the vertices be with edges , , , so and . To evaluate the algorithm tries midpoints in order. For , the call holds (take its own midpoint ), but fails: it would need a midpoint with a walk and of at most one edge each, and no such exists. For , we need and . The first holds with midpoint , since is true and is true because is an edge. The second holds with midpoint , since and are edges. So is true, matching the unique walk of three edges, which is at most . For the reverse query , no midpoint works, because vertex has no outgoing edges, so the only walk from is the empty one; the algorithm correctly answers false after exhausting all four midpoints.
Common mistake
(Square-logarithmic space does not mean fast)
The recursion above uses far less memory than a marking array when is large, but it repeats the same subproblems many times. A procedure whose memory is small may run in quasi-polynomial time, while a polynomial-time search such as breadth-first search may use linear memory. Neither bound implies the other, which is why these two resources must be tracked separately.
Counterexamples and sharpness
Each hypothesis in the preceding results is there for a reason, and the following examples show what fails without it.
Counterexample mode
The path-length bound n-1 cannot be lowered
A tempting claim is that walks of at most edges already decide reachability. In the directed path graph on vertices with edges , the only walk from to has exactly edges, so a machine that rejected after only edges would wrongly reject this yes-instance. The bound is therefore sharp.
The counter cannot be omitted. On the graph with edges and and with unreachable, a machine without a counter has a branch that alternates between and forever. That branch never halts, violating the convention that all branches halt. The counter ensures that this particular machine is a decider under that convention.
Counterexample mode
Logarithmic space is not logarithmic time
A tempting claim is that a machine using logarithmic work space also runs in logarithmic time. Consider the language of strings over consisting only of s. It is decidable in constant work space by one scan. Yet no deterministic machine can decide it in fewer than steps on . Starting at the left endmarker, the input head can reach cell only after at least steps. If the machine halted and accepted in fewer than steps, some cell would never be read. Changing that cell to would not alter the computation, so the machine would also accept a string outside the language, a contradiction.
The configuration count does not give polynomial time for larger space bounds. A machine using work cells over a binary alphabet can have distinct contents, so the same argument gives only an exponential-time simulation. This is consistent with, and does not contradict, the unresolved relation between and .
Concept lensAlgorithmic
One path, two resource measures
The reachability procedure stores a vertex and a counter, then rescans the input to verify each guessed edge. The counter limits a branch to a simple-path length, while space measures the cells reused during the search. A logarithmic work-space bound therefore does not assert that only logarithmically many computation steps occur.
Reading the reduction as an algorithm
The completeness proof starts with a fixed machine and takes its input as the variable input to the reduction. Fixing matters: its state set, alphabet and transition table have constant size, although the encoded configuration and the resulting graph grow with . A different language in NL may require a different machine and hence a different reduction; completeness does not promise one graph that simultaneously represents every machine.
A reduction has two jobs. The equivalence of answers is a mathematical statement about paths in the output graph. The space bound is a statement about the procedure that produces its encoding. For an adjacency matrix the producer loops over every ordered pair of labels and emits a bit. It can revisit the input and recompute a transition test for each pair. Neither the number of bits printed nor the time taken to print them is the same resource as the number of work cells simultaneously occupied. By contrast, storing the whole matrix on the work tape would destroy the claimed bound.
Worked example 3.4.6
(A tiny configuration graph)
Consider a nondeterministic machine whose start configuration has two legal successors: a rejecting configuration and an accepting configuration . Assume both halt. The reduction produces vertices and a fresh sink , with edges , , and . The path witnesses acceptance, even though the other branch rejects. If the edge is removed and no other transitions are added, is unreachable and all branches reject. The graph expresses existential acceptance, not a majority vote among branches.
Worked example 3.4.7
(An empty walk in the midpoint test)
Suppose the graph has vertices with the single edge . At level zero, is true because the empty walk has length zero, and is true because the edge exists. Therefore at level one, choosing proves . For neither candidate works: would require , while would require the same false statement. Allowing zero-length pieces is what makes the recurrence handle paths shorter than its upper bound without adding artificial self-loops.
The midpoint method does not construct a polynomial-time decision procedure merely because each stored label is short. It loops through candidate midpoints at every level, repeatedly recomputing subproblems. The work-tape analysis follows one active chain of recursive calls, whereas the time analysis counts the many calls made sequentially. This difference is why the recursion can save memory without settling whether NL equals L.
Additional practice and solutions
Quick check
(For the recursive reachability algorithm, compute the recursion depth and the number of stored vertex bits per frame for and for .)
Solution · Answer
For , , so there are levels, and vertices labeled need bits each. Three vertices per frame cost bits and the five frames cost bits for vertices. For , , giving levels, and labels need bits each. Three vertices cost bits per frame and six frames cost bits. The jump from to occurs because both the depth and the width of a frame increase when passes a power of two.
Quick check
(In the modified machine above with the transition removed, add an edge to its graph while leaving a rejecting halting configuration. Does the resulting graph give the correct answer from ? Explain.)
Solution · Answer
No. The added edge asserts that the rejecting halting configuration can reach acceptance in one step, although the machine has no such transition. It creates a path even though the modified machine has no accepting branch. The graph must contain sink edges exactly from accepting configurations.
Quick check
(In a graph with vertices and only edge , determine and .)
Solution · Answer
is true because the empty walk uses zero edges, at most . is false: no edge leaves , so the only walk from remains at .
Quick check
(A reduction prints a polynomial-length output using a logarithmic-size counter. Why does the output length alone not contradict its work-space bound?)
Solution · Answer
The output tape is write-only and is not charged as work space in this reduction model. The producer can emit each symbol and reuse its counter; it cannot subsequently use the output tape as readable memory. The logarithmic bound concerns the work cells used at one time, not the number of symbols eventually printed.