NL

Remarks

Example: directed reachability lies in $\mathrm{NL}$. An input is a directed graph $G$ with $n$ vertices and two vertices $s, t$. The machine stores the current vertex and a step counter, starts at $s$, and guesses an out-neighbour at each step. It accepts when it reaches $t$ and rejects after $n$ steps, using $O(\log n)$ cells. Some branch accepts exactly when $G$ has a path from $s$ to $t$.

Non-example: a machine that guesses a whole path and writes it on the work tape may use about $n \log n$ cells, so it does not show membership in $\mathrm{NL}$.

Directed reachability is NL-complete under logarithmic-space reductions. One has $\mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{P}$, where L is the class L and P is the class P. NL is closed under complement, by the Immerman–Szelepcsényi theorem.