ST-connectivity

The directed ST-connectivity problem asks whether a directed graph contains a graph path from specified vertices $s$ to $t$. A zero-length graph path is permitted, so $s=t$ is a positive instance. It is NL-complete under logspace many-one reductions.

For membership in NL, guess a graph path of at most $N-1$ edges, where $N$ is the number of vertices. Retain only the current vertex and a step counter. A reachable target has a simple graph path within that bound, and the stored indices use logarithmic space.

For hardness, take an NL machine on a fixed input and construct its configuration graph. Only polynomially many configurations are possible within the workspace bound, and all configurations and local transition edges can be enumerated with a logspace transducer. Add one target collecting the accepting configurations. The target is reachable from the initial configuration exactly when the original machine accepts. This translates any NL language into directed reachability while respecting the reduction's storage bound.

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.