Circuit Families and the Non-Uniform Model of Computation

A Boolean circuit is a device built for one input length. It is a directed acyclic graph whose sources are labelled either with an input variable $x_i$ or with a constant, whose internal vertices are gates drawn from a fixed basis of Boolean operations, and which has a single distinguished sink. Given a bit string of length exactly $n$, evaluation is one pass in topological order: read the sources, apply each gate to values already computed, read the sink. There are no loops, no state carried between runs, and no clock.

That is what remains of a machine after time is deleted. A Turing machine interleaves reading, branching and writing across many steps, reusing one tape cell for many purposes; a circuit must lay the whole computation out spatially, with a wire for every intermediate value that survives to be used. The compensation is that two resources become syntactic: the number of gates, called size, and the length of the longest source-to-sink path, called depth. Size is a proxy for total hardware, depth for the number of sequential steps a parallel machine would need, since all gates at the same level can fire at once.

Conventions that change the answers

Three conventions must be fixed before size and depth mean anything, and each one shifts the numbers.

The basis is the set of permitted gate types. A common choice is ${\wedge, \vee, \neg}$ with fan-in two, sometimes called the de Morgan basis. Another is ${\text{NAND}}$ alone, which is complete. The choice alters size by at most a constant factor when both bases are complete, but it alters the meaning of restricted classes completely; the basis and its effect on gate counts works through the conversions.

Fan-in is the number of incoming edges a gate may have. With fan-in two, a conjunction of $n$ literals costs $n-1$ gates. With unbounded fan-in it costs one gate of width $n$, and a whole disjunctive normal form with $2^n$ terms collapses to a depth-2 circuit of size $2^n + 1$. Depth-restricted classes such as $\mathrm{AC}^0$ are defined with unbounded fan-in precisely because the fan-in-two version of the same depth bound would be far weaker.

Whether constants $0$ and $1$ are available as sources matters only at the edges, but it does matter. Without them, a constant must be manufactured as $x \wedge \neg x$, which costs two gates and requires at least one input; a circuit family for a language that contains the empty string must handle $n = 0$ separately.

From a single function to a family

A decision problem is defined on strings of every length, and a circuit accepts only one length. Circuit complexity therefore attaches to a language $L$ a sequence $C_0, C_1, C_2, \ldots$ in which $C_n$ has $n$ inputs and $C_n(x) = 1$ exactly when $x \in L$. The sequence is the object of study; individual circuits are its members. A size bound is then a function $s : \mathbb{N} \to \mathbb{N}$ with $|C_n| \le s(n)$, and the class $\mathrm{SIZE}(s(n))$ collects the languages admitting such a family. Polynomial size gives

$$\mathrm{P/poly} = \bigcup_{c} \mathrm{SIZE}(n^c).$$

No bound means no classification. Every language whatsoever has a family: for each $n$, enumerate the accepted strings of length $n$ and take the disjunction of their minterms, which needs $O(n \cdot 2^n)$ gates. Without a size limit, circuits distinguish nothing, exactly as Turing machines without a time limit accept every recursively enumerable set. The resource bound does all the work.

The evaluator below makes the accounting concrete. Gates appear in topological order, and node indices below $n$ name inputs.

def evaluate(circuit, bits):
    """circuit: list of (op, left, right), topologically ordered.
    Inputs occupy indices 0..n-1; gate i is node n+i. 'not' ignores right."""
    n = len(bits)
    value = [int(b) for b in bits]
    for op, a, b in circuit:
        if op == 'and':
            value.append(value[a] & value[b])
        elif op == 'or':
            value.append(value[a] | value[b])
        elif op == 'xor':
            value.append(value[a] ^ value[b])
        else:                       # 'not'
            value.append(1 - value[a])
    return value[-1]

# Parity over n bits as a chain of XORs, five gates each in the de Morgan basis.
def parity(n):
    gates = []
    for i in range(1, n):
        src = i - 1 if i == 1 else n + len(gates) - 1
        gates.append(('xor', src, i))
    return gates

len(circuit) is the size, and every gate fires once, so evaluation costs time linear in size with $n$ processors or a single pass on one processor. A chain of $n-1$ XOR gates costs $5(n-1)$ gates in the de Morgan basis, since a two-input XOR expands to two negations, two conjunctions and one disjunction. Its depth grows linearly too, which is why parity sits in $\mathrm{NC}^1$ but not in constant depth; the switching lemma argument explains the second half of that statement.

What the non-uniform model can do that machines cannot

Nothing in the definition requires the family to be computable. There is no machine that must produce $C_n$ from $n$; the sequence simply exists. Three consequences follow, and they are the reason the model is useful and the reason it is dangerous.

A machine running in time $t(n)$ yields circuits of size $O(t(n)^2)$. The construction is a tableau: one row per time step, one column per tape cell that the head could reach, each cell’s next value computed by a small subcircuit from its three neighbours. The whole computation graph is acyclic and its size is the number of cells. This shows $\mathrm{P} \subseteq \mathrm{P/poly}$, so a superpolynomial circuit lower bound for a problem in $\mathrm{NP}$ would separate $\mathrm{P}$ from $\mathrm{NP}$ — a stronger statement than $\mathrm{P} \ne \mathrm{NP}$ itself.

The inclusion is strict in a blunt way. Take any undecidable language over a one-letter alphabet, such as the set of $n$ for which a fixed machine halts within $n$ steps on empty input. For each length there is exactly one string, so $C_n$ is either a constant-one gate or a constant-zero gate: a family exists trivially, even though no machine can decide the language. Since every language in $\mathrm{P}$ is decidable, $\mathrm{P} \subsetneq \mathrm{P/poly}$.

And diagonalization loses its grip. The classical separation of time classes works by simulating a machine and inverting its answer on its own description. Against a non-uniform class there is no machine to invert, only a sequence of devices; the lower bound must argue that every circuit of the given size fails on some input, which is a counting or combinatorial task rather than an algorithmic one. This asymmetry is the single largest obstacle in the area: the counting argument that settles the size of a typical function has no explicit witness.

Advice, and what the extra input means

$\mathrm{P/poly}$ has an equivalent formulation as $\mathrm{P}$ with polynomial advice: a language is in the class exactly when some polynomial-time machine $M$ and some sequence of advice strings $a_n$, with $|a_n| \le n^c$, satisfy $x \in L \iff M(x, a_n) = 1$ for every $x$ of length $n$. The circuit $C_n$ is the advice, compressed; the machine that evaluates a circuit description is a general-purpose circuit interpreter.

Advice is not help that a program could compute for itself. It is help that may encode arbitrary information about the input length, including information no algorithm could derive. The consequence is structural and severe. Karp and Lipton showed that if $\mathrm{NP} \subseteq \mathrm{P/poly}$ then the polynomial hierarchy collapses to its second level, $\Sigma_2^p$. The barriers that block the obvious proof strategies are what make that theorem a conditional rather than a tool.

Where the model stops matching hardware

The fixed-length restriction is the first mismatch. Real hardware is built once and runs on many lengths, usually with a length parameter supplied at runtime; a family of separate devices per length is a mathematical idealisation. Uniformity repairs this by demanding that a restricted machine, typically one working in logarithmic space, print the description of $C_n$ given $n$ in unary. Under that demand the classes become the parallel complexity hierarchy, and lower bounds become as hard as uniform ones.

Worst-case correctness is the second mismatch. A circuit is required to answer correctly on all $2^n$ inputs; nothing in the definition speaks about typical inputs, and an average-case analysis needs a distribution and a different notion of failure.

The last mismatch is quantitative and worth stating plainly. The best known lower bound for an explicit function over the full binary basis is only slightly above $3n$ gates, a result of Find, Golovnev, Hirsch and Kulikov from 2016, while the counting bound says that most functions need on the order of $2^n/n$. The gap between those two numbers, not any shortage of definitions, is the content of circuit complexity: the model is simple enough to state in a paragraph and hard enough that four decades of work have moved the explicit bound by a small constant factor.