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.

The University of Oxford computer science finals examination dated Wednesday 3 June 2015, Trinity Term 2015. The four-page original has three questions, on computability theory, time complexity and logarithmic space. The public examination-paper archive supplied by the University of Oxford contains it as 2015-complex.pdf. Questions 2 and 3 are marked corrected. Question 3(e) uses the word path in a graph without specifying whether repeated vertices are permitted; the even-length directed reachability proof uses directed walks with length counted with multiplicity.

Inductive counting certifies complete reachable sets while retaining only a count and a few vertex indices. For a directed graph with $N$ vertices and start $s$, let $R_k$ contain the vertices reachable in at most $k$ steps and write $r_k=|R_k|$.

Suppose the exact count $r_k$ is known. A nondeterministic computation can enumerate each vertex, guess which belong to $R_k$, and justify every positive guess by a path of length at most $k$. Requiring exactly $r_k$ justified vertices prevents omissions: false positives have no valid path certificate. To certify $v\notin R_{k+1}$, also check $v\ne s$ and that none of those enumerated vertices has an edge to $v$.

Starting from $r_0=1$, certify membership or nonmembership for each vertex and accumulate $r_{k+1}$. After $N-1$ stages every reachable vertex has been counted, since cycles can be removed from a reaching path. Loop counters and the current vertex use only logarithmic space; guessed paths are checked one edge at a time, and the full reachable set is never stored. This is the counting mechanism behind the Immerman–Szelepcsényi theorem.^[ref]

$\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.

Use Turing machines with a two-way read-only input tape, bounded by endmarkers, and a fixed finite number of read-write work tapes over a fixed finite alphabet. Work-tape cells count towards space complexity; the read-only input does not. For input length $n$, use $O(\log (n+2))$ to include the small-length cases.

$\mathrm{Logspace}$, or L, is the class of formal languages decided by a deterministic such machine using at most $c\log (n+2)$ work-tape cells for some fixed constant $c$. It must halt on every input and accept exactly the members.

$\mathrm{NLogspace}$, or NL, is the class of formal languages accepted by a Nondeterministic Turing machine with the same work-space bound on every computation branch. An input is accepted if and only if at least one branch accepts. One may require all branches to halt: the configuration graph has only a polynomial number of vertices, so a logarithmic space counter can stop any branch that has taken more steps than that bound. If an accepting computation exists, one exists with no repeated Turing machine configuration, so this convention does not change the complexity class.

In standard space complexity notation,

A logspace transducer is a deterministic Turing machine with a read-only input tape, $O(\log (n+2))$ read-write work space, and a write-only output tape. It emits symbols successively and cannot reread the output; that output is not charged as working memory. For a total function it must halt on every input. A logspace-computable function $f$ is a total function whose output $f(x)$ is produced by such a logspace transducer on input $x$.

A logspace many-one reduction $A{\le }_m^{\log }B$ is a logspace-computable function $f$ such thatfor every string $x$. The logarithmic space bound permits a polynomial-length output, even when that output does not fit in work space. Indeed, a halting logspace transducer cannot repeat its state, input-head position and work-tape contents and head positions: the unreadable output cannot affect its subsequent behaviour. There are only a polynomial number of such internal Turing machine configurations, hence a polynomial bound on the number of steps and output symbols.

To prove a formal language $B$ is NL-complete, first give an NL acceptance procedure for $B$. Then show every $A\in \mathrm{NL}$ has a logspace many-one reduction to $B$. Alternatively, reduce one already NL-complete formal language to $B$, using transitivity of logspace many-one reductions.

Transitivity requires logspace composition by recomputation, rather than storing the intermediate output. To compose $g$ with $f$, simulate the logspace transducer for $g$ with a virtual input $f(x)$. Retain its virtual input-head position in $O(\log n)$ bits. Whenever it asks for a symbol, rerun the logspace transducer for $f$ from the beginning and count its output symbols until that position is reached. Since $|f(x)|$ is polynomial in $n$, the simulated work space $O(\log |f(x)|)$ and all output-position counters are $O(\log n)$. Repeated runs reuse their storage. This proves closure under composition and explains why the hardness argument works.

The binary numeral system representation is taken to be canonical, with no leading zeroes, for each positive integer. Delimiters separate the components of a pair or triple. Syntax, positivity and this representation convention can all be checked in logarithmic space. The useful principle is that a large integer need not be stored in order to compute its digits one at a time.

First consider Add. Let $x_i,y_i,z_i$ denote the binary digits in position $i$, counting from the least significant position $i=0$ and taking out-of-range digits to be zero. Count the component lengths, and let $L$ be their maximum. Start with arithmetic carry $c_0=0$. For $i=0,\dots ,L-1$, computeReject if $s_i\ne z_i$ at any position. After the last position, reject if $c_L=1$; otherwise accept. The final arithmetic carry check prevents accepting a result with an omitted high digit, such as the false equality $11_2+11_2=10_2$ obtained by retaining only two binary digits.

The binary-addition carry invariant isIt holds initially and is preserved by the displayed one-column equations. At the end, it proves that the comparisons and the final arithmetic carry check succeed exactly when $x+y=z$. Each requested binary digit is recovered by scanning the corresponding input field and counting to its position. The length counters, position $i$ and scan counters require $O(\log n)$ bits, while $c_i$ and $t_i\in \{0,1,2,3\}$ require constant space. ThusFor Pal-Add, construct a logspace transducer producing the canonical binary numeral system representation of $x+y$. Put $m=\max (|x|,|y|)$. One least-to-most-significant pass using the same recurrence determines the final arithmetic carry $c_m$. Positivity and canonical representations imply that the sum's digit length isIndeed, one summand is at least $2^{m-1}$ and both are less than $2^m$. For each output position, from $\ell -1$ down to $0$, recompute the required sum digit from scratch: reset the arithmetic carry to zero and run the column recurrence from position $0$ up to the requested position, reading input digits by scans. Positions beyond the summands use zero digits, so position $m$ correctly emits the possible final arithmetic carry. Emit only the requested digit, then reuse the work space for the next position.

This produces most-significant-first output with $\ell \le m+1$ digits. It uses $O(\log n)$ work space because it retains only a fixed number of digit indices, lengths, scan counters and one arithmetic carry; it never stores the whole sum. A direct implementation with repeated whole-input scans uses at most $O(n^3)$ time complexity, which is sufficient here. Hence $(x,y)\mapsto \mathrm{bin}(x+y)$ is a logspace-computable function.

Finally simulate the assumed L decider for binary palindrome on this virtual output, using logspace composition by recomputation from part (b). Whenever the simulated input head asks for a digit, rerun the addition logspace transducer until it emits that digit. The virtual input length is $O(n)$, so both its work space and the addition work space are $O(\log n)$. The simulation accepts exactly when the canonical representation of $x+y$ is a binary palindrome. ThereforeEquivalently, one could directly compare the sum digits in positions $i$ and $\ell -1-i$, recomputing each digit by the same recurrence. This gives the same logarithmic space conclusion without ever writing the full sum on a work tape.

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.

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.