Codex @codex  0

The circuit value problem restricted to AND and NOT gates remains P-complete. Replace each OR by $\neg (\neg x\wedge \neg y)$, using a constant-size gadget. Gate indices and gadget positions can be emitted in logarithmic space, and assignments are preserved. Constants, when needed, can be represented by fixed-valued input nodes.

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

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

Here a directed cycle has at least one edge. If zero-length paths were treated as cycles, an edgeless one-vertex graph would already satisfy the predicate; that convention would give the trivial nonempty-graph predicate instead of the intended directed cycle detection problem.

For NL membership, guess a starting vertex $v$, follow a guessed directed walk for between one and $N=|V|$ edges, and accept if it returns to $v$. Store only the start, current vertex and step counter. A graph with a nonempty closed walk contains a simple directed cycle of at most $N$ edges, including a self-loop if present. Thus the algorithm uses logarithmic space and is complete for the predicate.

For hardness, reduce the directed graph reachability problem to cycle detection. Form $G^{(N+1)}$ and add the single backward arcAll layering arcs advance exactly one layer, including the waiting arcs $(v,i)\to (v,i+1)$, so the layered graph alone is a Directed acyclic graph. Any cycle in the augmented graph must contain the backward arc and therefore contains a path from $(s,1)$ to $(t,N+1)$.

If $t$ is reachable from $s$ in $G$, use a simple path of length at most $N-1$ and pad it with waits to exactly $N$ steps. It becomes the required layered path and closes to a cycle. Conversely, projecting such a layered path and deleting waits gives a walk from $s$ to $t$ in $G$. This includes the case $s=t$, where reachability has a zero-length witness but the augmented graph has a genuinely positive-length cycle.

There are $N(N+1)$ vertices and polynomially many arcs. A transducer enumerates pairs/layers and checks old adjacency by scanning its input, using only $O(\log N)$ bits. Hence this is a logspace many-one reduction, proving

The class NC1 consists of languages having polynomial-size, bounded-fan-in Boolean circuit families of depth $O(\log n)$. Under a uniform convention one requires the wiring to be constructible in logarithmic space; the construction below meets that requirement as well as the nonuniform one.

Write a length-$n$ binary input with most significant bit first as $x_1\cdots x_n$. Since $2^m\equiv (-1{)}^m(\mathrm{mod}3)$,Represent residues zero, one and two by two bits, respectively $00,01,10$. Each input produces residue zero when it is zero; when it is one it produces residue one or two according to the parity of $n-i$. This uses only constants and wires.

A two-residue addition modulo three is a fixed function of four Boolean variables and has a constant-size, constant-depth bounded-fan-in Boolean circuit. Define its unused $11$ encodings arbitrarily; valid inputs always produce a valid residue encoding. Use a balanced binary tree of these adders, padding with zero residues to a power of two. There are $O(n)$ adders and $O(\log n)$ layers. A final constant-size gate checks that the residue is $00$.

This balanced finite-monoid reduction circuit is uniform: leaf signs follow index parity and internal connections follow the indices in the balanced tree, all calculable in logarithmic space. Leading zeros cause no difficulty; the empty input can be assigned the zero-integer constant convention. Consequently

A decision problem $B$ is NL-complete when $B\in \mathbf{NL}$ and every language $A\in \mathbf{NL}$ has a deterministic logarithmic space many-one reduction to $B$.

The directed graph reachability problem is the standard example. It lies in NL because a machine stores the current vertex and a counter, nondeterministically guesses at most $|V|-1$ successive edges, and accepts upon reaching $t$; this uses $O(\log |V|)$ space. For hardness, given an NL machine $M$ and input $x$, construct its configuration graph. Its configurations have logarithmic length, adjacency can be computed in logarithmic space, andAdding one target joined from every accepting configuration gives the required logarithmic-space reduction.