= Solution
A decision problem $B$ is <NL-completeness>[NL-complete] when $B\in\mathbf{NL}$ and every language $A\in\mathbf{NL}$ has a deterministic <logarithmic space> many-one reduction to $B$.
The <directed graph reachability problem> is the standard example. It lies in NL because a machine stores the current vertex and a counter, nondeterministically guesses at most $|V|-1$ successive edges, and accepts upon reaching $t$; this uses $O(\!\log|V|)$ space. For hardness, given an NL machine $M$ and input $x$, construct its <configuration graph>. Its configurations have logarithmic length, adjacency can be computed in logarithmic space, and
$$
M\text{ accepts }x
\quad\Longleftrightarrow\quad
\text{an accepting configuration is reachable from the initial configuration}.
$$
Adding one target joined from every accepting configuration gives the required logarithmic-space reduction.
Back to article page
