Logarithmic Space, NL, and Reachability

By [L1], a configuration is specified by a state from a fixed finite set, one of $n+2$ input-head positions, the contents of $O(\log (n+2))$ work cells over fixed finite alphabets, and finitely many work-head positions among those cells.

The product of these choices is $(n+2{)}^{O(1)}$; enlarge its fixed constant to obtain a polynomial $p_M(n)$ bounding the reachable configurations.

If an accepting branch repeats a configuration, delete the segment between its two occurrences; the identical later configuration has the same possible continuation. Repeating this deletion yields a simple accepting path with fewer than $p_M(n)$ transitions.

Simulate the transducer for $g$ on a virtual input tape containing $f(x)$, retaining its work tape and its virtual input-head index $j$.

Whenever the simulation reads virtual cell $j$, rerun the transducer for $f$ on $(x,j)$ and supply its $j$th output bit; [L1] makes this a logarithmic-work-space subroutine.

Since $\mathrm{\mid }f(x)\mathrm{\mid }$ is polynomial in $\mathrm{\mid }x\mathrm{\mid }$, both $j$ and the simulated work tape use $O(\log \mathrm{\mid }x\mathrm{\mid })$ space. The streamed output is $g(f(x))$, so $x\in A$ iff it lies in $C$.

To decide $A$ from a deterministic or nondeterministic decider for $B$, run that decider on the same virtual input $f(x)$ rather than the transducer for $g$. The virtual-input access above preserves its deterministic or nondeterministic choice and its logarithmic work bound, proving the stated L or NL closure.

To decide STCON nondeterministically, retain a current vertex and a counter through $\mathrm{\mid }V\mathrm{\mid }-1$ moves, guessing an outgoing edge at each move and accepting on reaching $t$. A path exists exactly when one exists with at most $\mathrm{\mid }V\mathrm{\mid }-1$ moves.

For $A\in \mathrm{N}\mathrm{L}$, fix its machine $M$. On input $x$, make vertices from the valid configurations of $M$ on $x$, add a fresh target $t_x$, use legal transitions as arcs, and add an arc from every accepting configuration to $t_x$.

Both stored vertex labels and the counter have $O(\log \mathrm{\mid }V\mathrm{\mid })$ bits, so step 1.1 puts STCON in NL.

By [L1], there are polynomially many configuration names of $O(\log \mathrm{\mid }x\mathrm{\mid })$ bits. A transducer enumerates candidate pairs, checks locally whether one is a legal successor of the other, and streams the encoded graph, start configuration, and $t_x$ using $O(\log \mathrm{\mid }x\mathrm{\mid })$ work space.

A directed path from the start to $t_x$ is exactly an accepting computation branch of $M$ on $x$. Thus the transducer is an $A{\le }_{\log }\mathrm{S}\mathrm{T}\mathrm{C}\mathrm{O}\mathrm{N}$ reduction, which with step 2.1 proves NL-completeness.

On input $x$, encode a configuration by its state, input-head position, work contents, and work-head positions. There are only polynomially many syntactically possible encodings, by the same finite product count used in [L2]. Choose $r=O(\log (n+2))$ with $2^r$ at least that number.

Define $R(C,D,0)$ to test whether $C=D$ or $C\to D$ is one legal transition, and define $R(C,D,j+1)$ by enumerating every configuration $E$ and accepting exactly if both $R(C,E,j)$ and $R(E,D,j)$ hold. Induction on $j$ shows that it decides reachability by a path of length at most $2^j$.

A recursion frame stores $C,D,E$ and $j$, each using $O(\log (n+2))$ work bits; there are $r+1=O(\log (n+2))$ frames. Adjacency is recomputed from $M$ and the read-only input, never stored as a graph.

Enumerate accepting configurations $D$ and run $R(C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}},D,r)$. By step 2.1 this accepts exactly when $M$ has an accepting branch, and by step 3.1 it uses $O({\log }^2(n+2))$ charged work space.

By [L1], choose a nondeterministic read-only-input logspace decider for $A$.

Apply [L2] to this fixed decider. Its simulator is deterministic and uses $O({\log }^2(n+2))$ charged work cells.

The target class is exactly the local $\mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}({\log }^2(n+2))$ convention, so $A$ belongs to it. Since $A$ was arbitrary, the displayed inclusion follows.

Guess, in strictly increasing vertex-label order, $c$ distinct vertices different from $v$, together with for each an $s$-to-that-vertex walk of length at most $i$. Check each edge and count the listed vertices.

The current vertex, previous path vertex, path-length counter, list counter, and labels use $O(\log N)$ space. Thus this is an NL verifier.

If it accepts, [L1] puts all $c$ listed vertices in $C_i$. The given equality $c=\mathrm{\mid }{C}_i\mathrm{\mid }$ makes this list exhaust $C_i$, so $v\mathrm{\notin }{C}_i$. Conversely, when $v\mathrm{\notin }{C}_i$, list every member of $C_i$ with a witnessing bounded walk; the list has exactly the given length $c$, and the verifier accepts.

Start with $c_0=1=\mathrm{\mid }{C}_0\mathrm{\mid }$.

Assume inductively that the supplied $c_{i-1}$ equals $\mathrm{\mid }{C}_{i-1}\mathrm{\mid }$. Process every vertex $u$: either verify a positive path of length at most $i$ to $u$, or, for every $w$ with $w=u$ or $(w,u)\in E$, invoke the [L2] certificate for $w\mathrm{\notin }{C}_{i-1}$. Count the vertices in the first case and require the supplied total $c_i$.

The second case is sound: if $u\in C_i$, either $u\in C_{i-1}$ (the $w=u$ test fails) or the final edge of a length-at-most-$i$ walk has a predecessor in $C_{i-1}$, contradicting one of its [L2] certificates. Conversely, every $u\mathrm{\notin }{C}_i$ is outside $C_{i-1}$ and has no in-neighbor in $C_{i-1}$, while every $u\in C_i$ has a positive bounded path. Hence an accepted layer has $c_i=\mathrm{\mid }{C}_i\mathrm{\mid }$.

Induction from step 1.1 makes every accepted layer correct. Each nested certificate is checked by counters, vertex labels, and one bounded path at a time, so the verifier retains only $O(\log N)$ work space and reads a polynomial-size certificate once. At layer $N-1$, accept precisely when $t$ is absent from the certified list; by [L1] this is equivalent to nonreachability.

Fix an integer $a$ bounding $M$'s visited work cells by $as(n)$ for all sufficiently large $n$; handle the finitely many exceptional input lengths separately. Run the work-space constructor for $s(n)$ on a virtual unary input of length $n$; an address on the actual endmarked input provides this virtual input in $O(\log (n+2))$ space. A configuration records the fixed finite control, work symbols, work-head positions, and the endmarked input-head position. Since $M$ is fixed, choose a fixed constant $d$ so that every configuration within the cap has a padded binary description of length $K=d(s(n)+\lceil {\log }_2(n+2)\rceil +1)=O(s(n))$.

Use all $2^K$ binary strings as candidate vertex names and add a fresh target $t$. Invalid configuration names are isolated. Between valid names put an edge exactly for a legal transition of $M$ on the actual input $x$ within the work cap, and add an edge from each accepting configuration to $t$. The source is the actual initial configuration. Enumerating names, validating them, checking a transition, and recognizing an accepting state all take $O(K)$ space by direct scans of the fixed-length records and of $x$. Thus a path to $t$ exists exactly when $M$ accepts $x$. This constructs a well-defined finite graph for every input string $x$, without querying validity of any externally supplied STCON encoding.

Run the algorithm of [L2] on this implicit graph, with $N=2^K+1$. Its implementation only enumerates vertices and requests adjacency tests while checking bounded paths and successive reachable counts. Supply each such test by step 2.1. The previous layer's verified count, the current layer count, the finitely many vertex/loop indices, and one bounded path at a time have $O(\log N)=O(K)$ bits. The certificate checks are sequential nested loops of fixed depth, not a recursion stack through all layers. All loop and path lengths are bounded by polynomials in $N$, and each guessed certificate field has bounded length, so every branch halts. Nondeterministic choices generate the read-once certificate as needed; it is never stored. Soundness and completeness of [L2] now give an $O(s(n))$-space decider for $\bar{A}$.

This proves closure of $\mathrm{N}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s)$ under complement. By the definition of the co-class, closure implies equality with its co-class, since complementing twice recovers the original language. Finally $s(n)=\lceil {\log }_2(n+2)\rceil$ is work-space constructible: count the unary input in binary and compute the bit length, treating a power of two separately for the ceiling. This uses $O(\log (n+2))$ work cells. Its class is exactly NL under The classes L and NL, so the same equality specializes to $\mathrm{N}\mathrm{L}=\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{L}$.

The hypotheses here are exactly the hypotheses of the general clause in [L1].

Applying that clause gives $\mathrm{N}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))=\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))$, which is closure under complement.

For $0\le t\le B=B(n)$, encode each configuration by one-hot state bits, head-position bits $H_{t,r,j}$ for each tape $r$, and symbol bits $X_{t,r,j,a}$. Use positions $0\le j\le n+B+1$; no head can leave this interval within $B$ steps. There are exactly $n$ input nodes labeled $x_1,\dots ,x_n$; the initial row uses these, their negations, and constants for the input, blank cells, initial heads, and start state.

For each tape and symbol, compute the scanned-symbol bit $R_{t,r,a}={\bigvee }_j(H_{t,r,j}\wedge X_{t,r,j,a})$ with a binary OR chain. The fixed transition table applied to the state and these scanned-symbol bits gives constant-size Boolean formulas for the next state, write symbols, and movement directions. At a halting state define this circuit update to leave the entire configuration unchanged. This is an extension of the tableau update only; no transition from a halted machine is assumed.

At each cell, retain its old symbol unless its head bit is one, in which case use the computed write symbol. A new head bit is the OR of the old adjacent head bits conjoined with their computed movement directions; in a halted configuration keep its old head bit. At position zero also retain a head commanded to move left, as required by the right-infinite tape convention. Treat other out-of-range head bits as zero. These are constant-size formulas once the scanned-symbol bits are available. Induction on $t$ gives the genuine configuration until halting and its unchanged copy thereafter. Therefore the accepting-state bit at time $B$ equals one exactly when $M$ accepts $x$.

Each layer uses $O(n+B)$ gates: the tape count, alphabet, and state set are fixed, each scanned-symbol OR chain is linear, and each cell update has constant size. There are $B$ layers, so the size is $O(B(n+B))$, hence polynomial. All formulas use binary AND/OR and unary NOT. Designate the final accepting-state node as output.

Number nodes by initial-row order and then by time layer, with scanned-symbol chains before transition formulas and cell updates. Pad fixed formula blocks with unused constant nodes if necessary so that each block length is a fixed constant or fixed multiple of $n+B$. A node is addressed by its layer, block, position, and constant-size formula slot; all are $O(\log (n+2))$-bit integers. Fixed-degree arithmetic computes block offsets, adjacent positions, OR-chain predecessors, and the initial input label from these indices. Counting $n$ on unary input and evaluating the fixed polynomial $B(n)$ also use logarithmic space. These procedures answer SIZE, TYPE, predecessor, and output queries and emit the topological encoding. Thus [L2] gives logspace uniformity, including $n=0$ where the initial row has only constants.

Evaluate a valid circuit in its topological order, retaining its gate values in an array and applying the fixed basis operation at each gate. This takes time polynomial in the encoding length, so CIRCUIT-VALUE is in P.

For $A\in \mathrm{P}$, choose its fixed P decider $M$ and the family $(C_n)$ supplied by [L2]. On $x$ of length $n$, output $⟨C_n,x⟩$ by streaming the uniform circuit description and then copying $x$.

The transducer keeps only an $O(\log n)$-bit circuit-query index and its output position; [L2] answers each requested gate query in logspace. Thus $x\mapsto ⟨C_{\mathrm{\mid }x\mathrm{\mid }},x⟩$ is a logspace reduction, and it preserves acceptance.

Step 1.1 gives membership and step 2.1 gives hardness for arbitrary $A\in \mathrm{P}$; [L1] therefore gives P-completeness.

Suppose a machine has on one input both an accepting branch and a rejecting branch. By [L1] it accepts that input.

After terminal labels are swapped, the former rejecting branch is accepting, so the swapped machine also accepts the same input. The complement language instead rejects it.

Hence state swapping expresses “there exists a rejecting branch,” not “there is no accepting branch.” [L2] identifies the additional inductive-counting argument that genuinely proves the class equality.