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.

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.