= Solution
\b[Directed reachability is <NL-complete> under <logspace many-one reductions>.] For membership, let $N$ be the number of <vertices>. Store a current <vertex>, initially $v$, and a counter initially zero. Accept immediately if the current <vertex> is $v'$. Otherwise guess a next <vertex>, verify by scanning the <input> that the appropriate directed <edge> exists, move there and increment the counter. Reject a branch that has made $N-1$ steps without reaching $v'$.
Whenever a directed <walk> reaches $v'$, removing closed portions between repeated <vertices> produces a <path in a graph> with at most $N-1$ <edges>. Thus this bound preserves all yes-instances. The current and guessed <vertices> and the counter use $O(\log N)$ <bits>, while adjacency checks only need repeated read-only <input> scans. All branches halt, so directed reachability belongs to <NL>.
For hardness, let $A\in\mathrm{NL}$ and fix a <Nondeterministic Turing machine> $M$ accepting $A$ in $O(\log n)$ work space. On <input> $x$, construct its <configuration graph> $C_x$. A <vertex> is a possible <Turing machine configuration> within the fixed work-space bound. Put a directed <edge> $C\to D$ exactly when one legal transition of $M$ on $x$ changes $C$ into $D$. Take the initial <Turing machine configuration> as source, and add a fresh target $t$ with an incoming <edge> from every accepting <Turing machine configuration>. Then
$$
x\in A
\quad\Longleftrightarrow\quad
\text{the initial configuration reaches }t\text{ in }C_x.
$$
There are only a <polynomial> number of <Turing machine configurations>, by the count used in part (c). More importantly, their encodings have length $O(\log n)$. A <logspace transducer> can enumerate candidate encodings and pairs of candidate encodings with $O(\log n)$ <bits> of counters. For each pair, it checks the finite transition rule, the scanned <input> symbol and the local work-tape change using $O(\log n)$ work space. It emits the corresponding <adjacency matrix> entry or <edge>-list record. Invalid candidate encodings may be discarded or represented by isolated <vertices>.
The <configuration graph> is thus output by a <logspace transducer>, rather than stored in its work tapes. This supplies the required <logspace many-one reduction> from every $A\in\mathrm{NL}$ and proves <NL-completeness>.
$$
\boxed{\mathrm{Reachability}\text{ is NL-complete}.}
$$
Back to article page
