Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 59 / 3

A circuit size class $\mathrm{SIZE}(T(n))$ consists of languages whose length-$n$ indicator functions have Boolean circuits of size at most $T(n)$, for all sufficiently large $n$, over a fixed finite bounded-fan-in complete basis. The notation $\mathrm{SIZE}(O(T(n)))$ allows a constant factor. Input-node counting conventions do not affect the polynomial and exponential bounds here.

The nonuniform class P/poly isThere is no requirement that a uniform algorithm construct the Boolean circuits. Equivalently, a polynomial-time machine can receive polynomial-length advice depending only on the input length, and the advice need not be computable.

Choose an undecidable set $A\subseteq \mathbb{N}$, for example the set in the halting problem of indices of machines that halt on empty input, and define $U_A=\{1^n:n\in A\}$. For each length $n$, use a constant-zero Boolean circuit if $n\notin A$, and an AND of all $n$ input bits if $n\in A$. These Boolean circuits have size $O(n+1)$ and accept exactly $U_A$. Thus undecidable unary languages with linear-size circuits belong to P/poly.

Every NP language is decidable by enumerating its finitely many polynomial-length certificate encodings and running the polynomial-time verifier. If $U_A$ were decidable, testing $1^n$ would decide $A$, a contradiction. ThereforeThis separates the classes in the stated direction; it does not claim that NP is not contained in P/poly.

For each fixed input length, take the complete truth table of the language. For every accepted string $z\in \{0,1{\}}^n$, form the mintermAn OR of these minterms equals the indicator function, since $M_z(x)=1$ precisely at $x=z$. This is the truth-table upper bound for circuit size.

Generate the $n$ negated input wires once and share them. With $m\le 2^n$ accepted strings, use at most $m(n-1)$ binary AND gates and $m-1$ binary OR gates, besides the negations. Empty truth tables use a constant-zero Boolean circuit; length zero is handled by a constant Boolean circuit. ThusThis is an existence bound for a nonuniform circuit family, even when the language is undecidable. It supplies no algorithm for computing the truth tables of an arbitrary language.

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 $O(\log |C|)$ 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,

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