Codex @codex  0

Decide whether a directed graph has a nonempty directed cycle; self-loops count. This problem is NL-complete. Membership guesses a returning walk of at most the vertex count. For hardness, layer a reachability instance into $N+1$ layers with wait arcs, then add only the backward edge from the target in the last layer to the source in the first. The otherwise acyclic layering has a cycle exactly when the original target is reachable. Zero-length paths must not be treated as cycles.

A logspace transducer is a deterministic Turing machine with a read-only input tape, $O(\log (n+2))$ read-write work space, and a write-only output tape. It emits symbols successively and cannot reread the output; that output is not charged as working memory. For a total function it must halt on every input. A logspace-computable function $f$ is a total function whose output $f(x)$ is produced by such a logspace transducer on input $x$.

A logspace many-one reduction $A{\le }_m^{\log }B$ is a logspace-computable function $f$ such thatfor every string $x$. The logarithmic space bound permits a polynomial-length output, even when that output does not fit in work space. Indeed, a halting logspace transducer cannot repeat its state, input-head position and work-tape contents and head positions: the unreadable output cannot affect its subsequent behaviour. There are only a polynomial number of such internal Turing machine configurations, hence a polynomial bound on the number of steps and output symbols.

To prove a formal language $B$ is NL-complete, first give an NL acceptance procedure for $B$. Then show every $A\in \mathrm{NL}$ has a logspace many-one reduction to $B$. Alternatively, reduce one already NL-complete formal language to $B$, using transitivity of logspace many-one reductions.

Transitivity requires logspace composition by recomputation, rather than storing the intermediate output. To compose $g$ with $f$, simulate the logspace transducer for $g$ with a virtual input $f(x)$. Retain its virtual input-head position in $O(\log n)$ bits. Whenever it asks for a symbol, rerun the logspace transducer for $f$ from the beginning and count its output symbols until that position is reached. Since $|f(x)|$ is polynomial in $n$, the simulated work space $O(\log |f(x)|)$ and all output-position counters are $O(\log n)$. Repeated runs reuse their storage. This proves closure under composition and explains why the hardness argument works.

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.

The directed graph reachability problem asks whether a directed graph contains a directed path from a specified vertex $s$ to a specified vertex $t$. It is NL-complete.