Motivation
To show that a vertex is reachable in a directed graph, a nondeterministic machine can guess a path and check its edges while keeping only the current vertex and a step counter. The opposite claim seems harder: a failed guess proves only that one proposed path failed, not that every path fails. Nondeterminism accepts when at least one branch accepts; simply swapping accept and reject therefore does not complement the language.
The surprising idea is to count the vertices reachable within a bounded number of steps. Once the correct count is known, a machine can certify that it has listed all of them, even though each positive reachability certificate is checked one at a time. This yields .
Definitions
Definition 3.5.1
(Nondeterministic logspace machine)
A nondeterministic logspace machine uses work space on inputs of length ; its read-only input and write-only output tapes are not counted as work space. An input is accepted if some computation branch accepts. We require our machines to halt on all branches.
Definition 3.5.2
(Reachable layers and their sizes)
Use an explicit adjacency-matrix encoding for a directed graph , with vertices numbered , together with valid source and target indices. Its input length satisfies , and a logspace machine can validate the encoding and rescan the matrix to test an edge. With source , let
We include the empty walk, so and . A walk may repeat vertices; this causes no difficulty because we count vertices, not walks. Every reachable vertex has a simple path of length at most , so is the complete reachable set. Assume and the source and target are valid vertices; malformed graph encodings can be rejected deterministically before the main procedure.
Definition 3.5.3
(Directed reachability and STCON)
The directed reachability problem, STCON, asks whether is reachable from . Its complement asks whether . We use the standard fact that STCON is complete for NL under deterministic logspace many-one reductions. The accompanying reachability notes establish the configuration-graph reduction.
Theorem
Theorem 3.5.4
(Inductive counting and nonreachability)
The complement of directed reachability is in NL. Consequently . More generally, is closed under complement for each space-constructible bound ; the proof below explicitly establishes the logarithmic-space case.
The last, more general statement is named for context; its general configuration-count and space accounting are not proved here. We now prove the logspace claim without using that generalization.
Proposition 3.5.5
(What a certified count lets a scan conclude)
Given the correct value , a bounded nondeterministic scan can determine membership of any chosen vertex in using space: at least one branch survives, and every surviving branch returns the same correct answer. Repeating the scan for all vertices computes the correct with those same two guarantees. The assertion requires the supplied count to be correct.
Proof
Replace a stored set by a verified quota
The machine is not trying to store the reachable set in a compressed bit vector. It stores its cardinality and repeatedly reconstructs a certificate for the whole set. These are different resources: an arbitrary subset of vertices could need membership bits, while its cardinality needs only logarithmically many. The small count alone would reveal almost nothing, but it becomes powerful when combined with sound positive membership certificates.
For each vertex, choosing “not listed” is only an omission, never a certificate of nonmembership. Choosing “listed” carries an obligation to exhibit a checked walk. The checked list is consequently a subset of the true reachable set. If it has the already known cardinality of that set, it must be the entire set. This is a finite-set implication, not an assumption that nondeterministic machines can verify arbitrary negative statements.
Two quantifiers must remain separate. Every branch that survives all checks must be correct; otherwise even one spurious accepting branch would ruin soundness. At least one branch must survive whenever the algorithm ought to proceed; otherwise a correct claim might be rejected solely because all guesses were required to do something impossible. Listing all truly reachable vertices with valid walks supplies that second property. The construction proves both, rather than informally declaring a guessed list exhaustive.
Advance one reachable layer
Proof
(Advancing the count by one layer)
First suppose the correct integer has already been stored. We describe a bounded nondeterministic procedure for computing . For each candidate vertex , scan vertices in order. At each , guess either “listed” or “not listed.” If listed, guess a walk of at most edges from to and verify it by storing only its current vertex, its length, and the next guessed vertex. Reject immediately if a claimed edge is absent or the walk does not end at . Increase a counter for every listed .
During this same scan, set a flag if a listed vertex equals or has an edge to . When the scan ends, reject unless the number listed equals the stored . Otherwise the flag is the correct answer to whether . Indeed, all listed vertices have verified witnesses and belong to . They are distinct because is scanned once. A subset of with exactly members is the whole of . Conversely there is a successful choice of witnesses: list every vertex of with a valid walk and list no other vertex. The equivalence
then justifies the flag.
Count the candidates whose flags are set; this is . Each scan may make new nondeterministic choices, but every scan that survives the cardinality check lists exactly . Therefore every surviving branch computes the same correct next count. There is at least one surviving branch, because valid witness walks exist for every listed reachable vertex. Starting with , repeat for .
The old count must remain available throughout this outer pass. Keep a separate accumulator for the next count and reset the local listed counter for each candidate . Only after every candidate has been processed may the next count replace the old count. Reusing a single counter too early would make later candidates compare their lists against a partially computed quantity rather than against . This implementation detail is part of preserving the induction invariant, while still requiring only a fixed number of small counters.
The positive-walk verifier can choose to stop after any length from zero through . A branch choosing zero checks that its current vertex is already the requested endpoint; another guesses a next vertex, checks the edge and increments its length. Reaching the length bound without the correct endpoint rejects. There is no unbounded search hidden inside the membership certificate. In particular, the source always has the empty-walk certificate, including at the initial layer.
Finally scan all once more, using witnesses of length at most and the verified count . Accept exactly when the scan survives and does not list . If is unreachable, a correct list gives an accepting branch. If is reachable, every surviving list contains it, and all other branches reject. This proves correctness in both directions.
At any moment the machine stores , the current and , a current walk vertex and length, a few counters bounded by , the current count and flags. Each needs bits. The matrix input can be rescanned to test an edge, and no list of vertices or paths is retained. Loops and witness lengths are bounded, so every branch halts. The explicit encoding has , so this is space. A succinct graph encoding may have exponentially many vertices relative to its input length and needs a separate analysis; this proof does not cover it.
Proof X-ray
Why the cardinality check carries the argument
Two things make the layer step work. First, the check that exactly distinct verified vertices were listed turns positive certificates into an exhaustive list: a subset of with elements is , so the flag is correct on every surviving branch, and listing all of shows that a surviving branch exists. Second, correctness is inherited. The hypothesis that the stored is correct is used at every layer, and it holds because every surviving branch of the previous layer computed the correct count, starting from . The old count must stay intact while the new one accumulates; overwriting it early would compare lists with the wrong number. Without a trusted count the check proves nothing, as the quota example shows.
Proof
(From nonreachability to coNL)
To pass from nonreachability to all of coNL, let and let be a deterministic logspace reduction to STCON. Then exactly when is a nonreachability instance. A logspace machine can simulate the nonreachability algorithm on the virtual output of , recomputing requested output bits as needed rather than storing the whole graph. Thus , showing . Taking complements gives the reverse inclusion.
This simulation has polynomially many virtual input positions for the usual halting logspace transducer: a repeated internal configuration would otherwise repeat forever, while the output tape cannot be read to change future behavior. A requested output bit can therefore be obtained by rerunning the transducer with a position counter. Keeping that counter and the nonreachability machine's work tapes simultaneously still uses logarithmic space in the original input length. This is why closure under logspace reductions does not require materializing their whole output.
Worked examples
Worked example 3.5.6
(Counting reachable vertices in layers)
Take vertices and edges , , , with source . Then , and . The counts are . For candidate at stage , a scan must list exactly the three members of with witnesses. The edge sets the flag. A scan listing only and cannot falsely classify as absent: it fails the count check.
Worked example 3.5.7
(An unreachable target with a cycle)
Let the graph have edges and , with isolated vertex , source and target . The first two reachable sets are and ; all later reachable sets remain . Although there are infinitely many walks around the cycle, a shortest witness for each reachable vertex has at most one edge. A valid final scan lists and omits , so some branch accepts nonreachability.
Worked example 3.5.8
(An unchecked smaller quota could hide a reachable vertex)
Use five vertices, source one, and edges , , . At layer one the true reachable set is and its count is three. When testing whether four belongs to the next layer, a scan listing only one and two has valid positive certificates, but misses the predecessor three. With the correct quota it rejects because it listed two vertices, not three. If the machine were allowed to guess the smaller quota two without justification, that same scan would survive and wrongly report four absent. The layer-by-layer construction rules this out by deriving every quota from its certified predecessor.
Common mistakes
Common mistake
(A guessed count is not a certified count)
A guessed count is not trustworthy by itself. The procedure starts with the known value and verifies each next count using the preceding correct value. Nor can one simply guess that an unlisted vertex is unreachable: the cardinality check forces every surviving scan to include all reachable vertices.
Common mistake
( does not give )
The statement does not imply ; it provides a nondeterministic algorithm for the complement, not a deterministic one.
Counterexample mode
Counting a vertex twice defeats the quota
Suppose the scan were allowed to list the same vertex more than once, so that only the number of verified claims is compared with . Use five vertices, source and edges , , , so and . A scan that lists vertex twice and vertex once makes three verified claims, each with a valid walk (the empty walk for , the edge for ), so it passes the count check. It never lists , so no listed vertex has an edge to , and the flag for stays unset. The scan therefore reports , although is a walk of length two. Listing vertices in increasing order, each at most once, makes the verified claims a set, and a subset of with elements must be all of .
Summary
Positive path certificates plus an already certified count force an exhaustive list without storing it. Repeating that observation for successive path-length bounds proves directed nonreachability is in NL. The result is an existence statement about nondeterministic logspace algorithms; it does not supply a deterministic logspace algorithm for directed reachability.
Exercises
Quick check
(For edges , , , and isolated vertex , find from source and decide whether target is reachable.)
Build one layer at a time.
Solution · Answer
The reachable sets are , , , and , giving counts . Vertex is unreachable.
Quick check
(Why does the verification scan need to process each vertex only once? What can go wrong if the same vertex is counted repeatedly?)
Compare the number of claims with the number of distinct vertices.
Solution · Answer
Processing each once makes the number of verified claims the size of a set. If repeats counted, one reachable vertex could be listed multiple times, filling the quota while another reachable vertex was omitted.
Quick check
(A student claims that after a scan of vertices, failure to find a path to proves nonreachability. Identify the missing condition.)
A branch may simply not list a vertex.
Solution · Answer
A branch may choose not to list a reachable vertex or guess a bad witness. The scan must verify every positive claim and verify that the number of distinct listed vertices is the already certified correct reachability count; otherwise omission of proves nothing.
Quick check
(In a one-vertex graph with source and target both equal to that vertex, should nonreachability accept? Explain the zero-length case.)
Is the empty walk a walk?
Solution · Answer
No. The empty walk shows that the source reaches itself, so contains the target. Since , the final list is and every valid branch rejects nonreachability.
Quick check
(If and is also NL-hard under deterministic logspace many-one reductions, show that is coNL-hard under the same kind of reductions.)
Start from an arbitrary and complement it.
Solution · Answer
Let , so . By hardness there is a deterministic logspace with iff . Taking complements yields iff . Thus every coNL language reduces to .