= Solution
It suffices to recognize non-reachability in <NL>, since directed reachability is NL-complete. Let $c_k$ be the number of vertices reachable from $s$ by a directed path of length at most $k$. Clearly $c_0=1$. The <inductive counting> argument computes and verifies $c_{k+1}$ from $c_k$ using logarithmic space.
For each vertex $v$, reachability within $k+1$ steps has an NL certificate: guess such a path. Non-reachability within $k+1$ steps can be certified relative to the trusted value $c_k$ by enumerating vertices $u$, exhibiting paths of length at most $k$ to exactly $c_k$ distinct vertices, and checking that none is $v$ or has an edge to $v$. Because there are exactly $c_k$ reachable vertices, this list cannot omit a reachable predecessor. Counters, vertex names and one guessed path need only logarithmic space. Repeating this check in a fixed vertex order and counting the positive cases produces the exact $c_{k+1}$.
After $|V|-1$ rounds, the procedure knows the number of all vertices reachable from $s$. It accepts non-reachability of $t$ after certifying, by the same complete enumeration, that $t$ is absent. Thus the complement of directed reachability belongs to NL. Since every NL language reduces to reachability and log-space reductions are closed under complementation, this proves the <Immerman–Szelepcsényi theorem>
$$
\boxed{\mathbf{NL}=\mathbf{co\text{-}NL}.}
$$
Back to article page
