Logarithmic Space, NL, and Reachability: Examples and Counterexamples

The first requested virtual symbol is $0$. Maintain a counter to find $\mathrm{\mid }f(x)\mathrm{\mid }=2n+2$ and recompute the final virtual symbol, which is $x_1$ when $n>0$ and $\mathrm{\#}$ when $n=0$. Forward and backward scans emit $f$, while two endpoint scans emit $g$; both use at most logarithmic work space and halt on every input.

Thus the composed output is $0x_1$ for $n>0$ and $0\mathrm{\#}$ for $n=0$, exactly $g(f(x))$; it used only counters and a reread of $x$.

The word $f(x)$ lies in $B$ exactly when $x$ starts with $1$, and $g(y)=01$ exactly when $y$ starts with $0$ and ends with $1$; the empty input maps to $00$. Thus these are total logspace reductions $A{\le }_{\log }B{\le }_{\log }C$, and the explicit virtual computation illustrates their composition in [L2].

On $01$, $g_1=\mathsf{N}\mathsf{O}\mathsf{T}(0)=1$ and $g_2=\mathsf{A}\mathsf{N}\mathsf{D}(1,1)=1$, agreeing with the machine's accepting final state.

For every two-bit input, $\mathsf{A}\mathsf{N}\mathsf{D}(\mathsf{N}\mathsf{O}\mathsf{T}(x_1),x_2)=1$ exactly when $x_1=0$ and $x_2=1$. Number the input nodes $1,2$ and the NOT and AND nodes $3,4$, with predecessor lists $(1)$ and $(3,2)$ and output node $4$. This fixed circuit can be emitted in constant work space; it is a direct circuit for the promised computation, illustrating the existence assertion in [L1].

The pair $⟨C,01⟩$ is therefore a yes-instance of Circuit Value, illustrating the acceptance-preserving reduction in [L2].

The original accepting leaf makes the original machine accept $x$ by [L1].

After labels swap, the original rejecting leaf is accepting, so [L1] makes the swapped machine accept $x$ as well.

Since $x$ is in the original language, it is not in its complement; step 2.1 therefore contradicts the proposed complementing behavior, as asserted in [L2].