NL (complexity, $\mathbf{NL}$)

$\mathbf{NL}$ consists of decision problems solvable by a nondeterministic logarithmic space computation.

A decision problem is NL-complete when it belongs to NL and every problem in NL reduces to it by a deterministic logarithmic-space many-one reduction.

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.

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.

Decide whether a finite directed graph has an even-length directed walk from a specified source $s$ to a specified target $t$. Vertices may repeat and a zero-length walk is allowed. The NL-completeness proof uses the graph of pairs $(v,b)$ with $b\in \{0,1\}$ tracking integer parity: every original edge flips $b$, and acceptance means reaching $(t,0)$ from $(s,0)$. At most $2|V|-1$ steps are needed in the parity graph. For hardness, subdivide every edge of an ordinary reachability instance into two directed edges. Both constructions are computable by logspace transducers. Requiring a simple path in a graph in the original graph changes the question; deleting an odd closed portion need not preserve integer parity.

The configuration graph of a machine on a fixed input has one vertex for each machine configuration and a directed edge for each valid computation step.

$\mathbf{co}\text{-}\mathbf{NL}$ consists of complements of languages in NL.

The Immerman–Szelepcsényi theorem states that $\mathbf{NL}=\mathbf{co}\text{-}\mathbf{NL}$. Its proof uses inductive counting of reachable configurations.

Inductive counting certifies the number of vertices reachable within successively larger path-length bounds. Knowing the exact earlier count lets a logarithmic-space nondeterministic machine certify that no reachable predecessor has been omitted.