Circuit value problem Created 2026-10-07 Updated 2026-10-14
Given a finite acyclic Boolean circuit and its input assignment, determine the output bit. Topological gate evaluation places the problem in P; it is a standard P-complete problem under logspace many-one reductions. Boolean circuit evaluation is different from Circuit satisfiability problem, which asks whether some assignment succeeds.
Logspace composition by recomputation 2026-10-31
To simulate on the virtual input , store the simulated input-head position and rerun the logspace transducer for whenever an input symbol is requested. Count emitted symbols until the requested position is reached. The intermediate output has polynomial length, so its positions take bits, and the work space of is also . Storage used by successive recomputations is reused. This proves closure of logspace-computable functions under composition and transitivity of logspace many-one reductions.
A logspace transducer is a deterministic Turing machine with a read-only input tape, 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 is a total function whose output is produced by such a logspace transducer on input .
A logspace many-one reduction is a logspace-computable function such thatfor every string . 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 is NL-complete, first give an NL acceptance procedure for . Then show every has a logspace many-one reduction to . Alternatively, reduce one already NL-complete formal language to , using transitivity of logspace many-one reductions.
Transitivity requires logspace composition by recomputation, rather than storing the intermediate output. To compose with , simulate the logspace transducer for with a virtual input . Retain its virtual input-head position in bits. Whenever it asks for a symbol, rerun the logspace transducer for from the beginning and count its output symbols until that position is reached. Since is polynomial in , the simulated work space and all output-position counters are . Repeated runs reuse their storage. This proves closure under composition and explains why the hardness argument works.
Directed reachability is NL-complete under logspace many-one reductions. For membership, let be the number of vertices. Store a current vertex, initially , and a counter initially zero. Accept immediately if the current vertex is . Otherwise guess a next vertex, verify by scanning the input that the appropriate directed edge exists, move there and increment the counter. Reject a branch that has made steps without reaching .
Whenever a directed walk reaches , removing closed portions between repeated vertices produces a path in a graph with at most edges. Thus this bound preserves all yes-instances. The current and guessed vertices and the counter use bits, while adjacency checks only need repeated read-only input scans. All branches halt, so directed reachability belongs to NL.
For hardness, let and fix a Nondeterministic Turing machine accepting in work space. On input , construct its configuration graph . A vertex is a possible Turing machine configuration within the fixed work-space bound. Put a directed edge exactly when one legal transition of on changes into . Take the initial Turing machine configuration as source, and add a fresh target with an incoming edge from every accepting Turing machine configuration. ThenThere are only a polynomial number of Turing machine configurations, by the count used in part (c). More importantly, their encodings have length . A logspace transducer can enumerate candidate encodings and pairs of candidate encodings with bits of counters. For each pair, it checks the finite transition rule, the scanned input symbol and the local work-tape change using work space. It emits the corresponding adjacency matrix entry or edge-list record. Invalid candidate encodings may be discarded or represented by isolated vertices.
The configuration graph is thus output by a logspace transducer, rather than stored in its work tapes. This supplies the required logspace many-one reduction from every and proves NL-completeness.
The printed question calls the route a path in a graph and writes , without specifying whether repeated vertices are allowed.[ref]
Computational Complexity examination paper of the University of Oxford (2015). Printed p. 4, Question 3(e)
Use the computational reachability convention that a permitted route is a directed walk: repeated vertices are allowed and length counts traversed edges with multiplicity. This matters for the integer parity restriction, because deleting a closed portion of odd length can change the integer parity. The proof below establishes the stated NL-completeness for this convention; it does not establish that claim for a simple path in a graph.For membership of even-length directed reachability in NL, form the conceptual parity graph with vertex setand directed edgesAfter a directed walk of length from , the second coordinate equals . Therefore there is an even-length directed walk from to in exactly when is reachable from in this parity graph. It has vertices. Guess successive edges while storing the original current vertex, one parity bit, and a counter bounded by . If the target pair is reachable, it has a simple path in a graph in this enlarged graph of at most edges. This is an NL procedure; the parity graph need not be materialized.
For NL-hardness, reduce directed reachability by subdividing each directed edge with its own new vertex :Retain as the endpoints and add no other edges. Every original directed walk of length becomes a directed walk of even length . Conversely, a directed walk between original vertices in the new graph must alternate original and subdivision vertices. Compressing each two-edge segment recovers a directed walk in . HenceA logspace transducer enumerates the original edges, labels each new vertex by its edge endpoints or its position in the input, and emits its two replacement edges. All labels and counters take bits, and the output is of polynomial size. Thus this is a logspace many-one reduction, provingAs in ordinary reachability, a zero-length directed walk is permitted, so is an immediate yes-instance. Both the membership procedure and the subdivision many-one reduction preserve that case.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 2 b Solution Created 2026-10-03 Updated 2026-11-05
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 , follow a guessed directed walk for between one and edges, and accept if it returns to . Store only the start, current vertex and step counter. A graph with a nonempty closed walk contains a simple directed cycle of at most 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 and add the single backward arcAll layering arcs advance exactly one layer, including the waiting arcs , 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 to .
If is reachable from in , use a simple path of length at most and pad it with waits to exactly 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 to in . This includes the case , where reachability has a zero-length witness but the augmented graph has a genuinely positive-length cycle.
There are vertices and polynomially many arcs. A transducer enumerates pairs/layers and checks old adjacency by scanning its input, using only bits. Hence this is a logspace many-one reduction, proving
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 3 c Solution Created 2026-10-03 Updated 2026-10-07
The AND-NOT circuit value problem belongs to P: validate the Boolean circuit and evaluate its gates in a topological ordering. Evaluation takes polynomial time even if its description is not already in a topological ordering.
For P-completeness we use logspace many-one reductions. Start from the supplied circuit value problem over the usual AND (logical conjunction), OR (logical disjunction) and NOT (negation) basis. Retain AND and NOT gates, and replace every OR gate by the De Morgan's laws gadgetThis adds only a constant number of gates per old gate, preserves its truth value for all inputs and keeps the Boolean circuit acyclic. If the format includes constant source nodes, replace them by additional input nodes assigned fixed bits zero and one; these are inputs, not disallowed gates. Larger fan-in gates can first be replaced by binary trees of their inputs.
To output the new description, keep the old gate index and a constant-size gadget position, rescan old references when necessary, and assign consistent new indices to each gadget's terminal output. These counters and references occupy bits; the input assignment is copied with any constant-source bits appended. Thus the construction is a logspace many-one reduction preserving acceptance. Since Boolean circuit Value is P-complete under such reductions,
P-completeness Created 2026-10-07 Updated 2026-10-31
A language in P to which every P language has a logspace many-one reduction. The reduction strength matters: using arbitrary polynomial-time reductions instead would make completeness trivial for nontrivial P decision problems.
ST-connectivity Created 2026-09-24 Updated 2026-11-05
The directed ST-connectivity problem asks whether a directed graph contains a graph path from specified vertices to . A zero-length graph path is permitted, so is a positive instance. It is NL-complete under logspace many-one reductions.
For membership in NL, guess a graph path of at most edges, where 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.