Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 3 / d / Solution

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^{\prime }$. 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^{\prime }$.

Whenever a directed walk reaches $v^{\prime }$, 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. ThenThere 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.