Gate Basis, Fan-In, and What Circuit Size Actually Counts

A circuit size bound is meaningless until the basis is fixed. The same function can cost three gates or eleven, and a result proved for one gate set does not transfer to another without an argument. That argument exists and it is cheap — for complete bases, size changes by a constant factor and nothing else — but the constant matters when lower bounds are stated as exact coefficients, and the notion of a “constant factor” collapses entirely once depth is bounded and fan-in is left unbounded.

Two bases, one function

Consider the function that outputs 1 when at least two of three inputs are 1, the majority function on three bits. Write it in disjunctive normal form: three minterms, each a conjunction of three literals, joined by two disjunctions.

With unbounded fan-in $\wedge$ and $\vee$ plus $\neg$, the circuit has five gates: three conjunctions of width three, one disjunction of width three, and the negations pushed to the leaves by De Morgan. No gate has more than one level of logic behind it.

With fan-in two, each width-three conjunction needs two binary $\wedge$ gates, and the width-three disjunction needs two $\vee$ gates. The count rises to seven, plus two $\neg$ gates for the negated literals, so nine.

With NAND alone, each binary NAND is one gate, but the negation of a literal costs a NAND with both inputs tied to the same wire, and the final disjunction must be rewritten as a negated conjunction of negations. A direct translation of the same formula lands somewhere in the low teens. All three circuits compute the same function on all eight inputs; the numbers differ by construction, not by insight.

The transfer principle that licenses ignoring such differences is this: if $\mathcal{B}_1$ and $\mathcal{B}_2$ are both complete — each can express every Boolean function — then there are constants $c_1, c_2$ such that for every $f$ and every circuit over $\mathcal{B}_1$ of size $s$, there is a circuit over $\mathcal{B}_2$ of size at most $c_1 s + c_2$, and vice versa. Completeness is what makes the constants exist; it does not make them equal to one.

The cost of eliminating a gate type

Converting between bases is mechanical and the gate count of each step is worth knowing, because these steps reappear inside lower-bound proofs where the overhead must be tracked.

Removing XOR from a de Morgan circuit is the most expensive common conversion. The identity $a \oplus b = (a \wedge \neg b) \vee (\neg a \wedge b)$ expands one gate into five. A parity circuit over $n$ inputs built from a chain of two-input XORs therefore costs $5(n-1)$ gates in ${\wedge, \vee, \neg}$, not $n-1$. This factor of five is why parity lower bounds are usually stated in the de Morgan basis with the constant absorbed, or in a basis where XOR is primitive.

Removing AND and OR in favour of NAND uses De Morgan’s laws. Each $\wedge$ gate becomes a NAND followed by an inverter, and each $\vee$ gate becomes inverters on both inputs feeding a NAND. An inverter is a NAND with both inputs joined to the same wire. In the worst case each binary gate of the source circuit becomes three NANDs, so the constant is at most three per gate.

Pushing negations to the inputs uses the identities $\neg(a \wedge b) = \neg a \vee \neg b$ and $\neg(a \vee b) = \neg a \wedge \neg b$, applied from the output backwards. Each application swaps a gate type and moves a negation to both children. A gate may accumulate two negations that cancel, so the number of gates does not increase, but each input wire may end up negated, which is free only if negated literals are permitted as sources.

Constants are the smallest conversion and the easiest to overlook. If the source circuit uses a constant-0 source and the target basis has none, it can be built as $x \wedge \neg x$ for any input $x$, costing two gates and one inverter, or as the NAND of a wire with itself, costing one gate. A family that must handle $n=0$ has no input to abuse this way and needs an explicit constant source.

Why fan-in changes the class, not just the count

With fan-in two, a depth-$d$ circuit has at most $2^d$ leaves, so it can depend on at most $2^d$ inputs. With unbounded fan-in, a depth-2 circuit already has $2^n$ leaves: the disjunctive normal form of any function is a single OR over minterms, each minterm a single AND. Every Boolean function whatsoever lies in depth 2 with unbounded fan-in, at a size of $2^n + 1$ gates. That single observation is the reason $\mathrm{AC}^0$, $\mathrm{ACC}^0$ and $\mathrm{TC}^0$ are defined with unbounded fan-in gates and polynomial size, rather than with bounded fan-in and constant depth.

The bounded-fan-in counterpart is $\mathrm{NC}^0$, and it is dramatically weaker: a constant-depth, fan-in-two circuit of polynomial size can only depend on constantly many inputs, so it computes essentially local functions. Parity, majority, and even the OR of $n$ bits are outside it, while all three are inside $\mathrm{AC}^0$ — OR of $n$ bits is one gate. The depth hierarchy is built on exactly this distinction, and the choice of fan-in convention is what makes the hierarchy non-trivial at the bottom.

There is a conversion in the other direction, and its cost is the price of simulating wide gates with narrow ones. A fan-in-$k$ AND becomes a binary tree of depth $\lceil \log_2 k \rceil$ and $k-1$ gates. For a depth-$d$, size-$s$ unbounded circuit this yields a fan-in-two circuit of size $O(s)$ and depth $O(d \log s)$, so $\mathrm{AC}^i \subseteq \mathrm{NC}^{i+1}$ and the two hierarchies interleave. The extra logarithmic factor is not an artefact of a lazy construction; it is the standard cost of binary reduction.

from functools import reduce

def and_tree(wires):
    """Binary reduction: k inputs cost k-1 gates, depth ceil(log2 k)."""
    level = list(wires)
    gates = []
    while len(level) > 1:
        nxt = []
        for i in range(0, len(level) - 1, 2):
            gates.append(('and', level[i], level[i + 1]))
            nxt.append(gates[-1])          # placeholder: identity of the new gate
        if len(level) % 2:
            nxt.append(level[-1])          # odd wire passes through unchanged
        level = nxt
    return gates

# A k-input AND costs exactly k-1 gates whether built as a tree or a chain;
# only the depth differs: ceil(log2 k) versus k-1.

Both shapes use $k-1$ gates. The tree’s depth is logarithmic, the chain’s is linear, and the gate count is identical — a clean example of size and depth being independent resources.

Size as a measure of work

Two bounds justify treating gate count as the right resource. Each gate of a circuit corresponds to one operation in a straight-line program, a sequence of assignments in which every variable is written once. A circuit of size $s$ and an $s$-line straight-line program with the same basis are the same object viewed twice, so size is the natural measure of sequential work with no branching. And a Turing machine with a time bound $t(n)$ converts to a circuit family of size $O(t(n) \log t(n))$ when the tape alphabet and head movement are encoded carefully, which is why polynomial size corresponds to polynomial time and why $\mathrm{P} \subseteq \mathrm{P/poly}$ holds. The family construction spells out the tableau; the point here is that the polynomial is not tight and never has been, since the conversion is used for inclusions and not for exact resource transfer.

Where the constant factor argument fails

Three places. First, in explicit lower bounds: a theorem saying every circuit for a function needs $3.1n$ gates over one basis does not immediately give $3.1n$ over another, only $3.1n/c$ for the conversion constant $c$, which may round to a weaker statement. Papers state the basis precisely for this reason.

Second, in restricted classes. Constant-factor equivalence between complete bases holds for unrestricted circuits, and fails the moment a structural restriction is imposed that one basis satisfies more easily. A monotone circuit over ${\wedge, \vee}$ has no negations at all; the equivalent over a complete basis may need negations on every wire, and the restriction is not preserved by the conversion. Monotone complexity is a separate measure with separate lower bounds, treated in Razborov’s approximation method.

Third, in basis-dependent primitives. A basis containing XOR and a basis containing only NAND are both complete, but the first expresses parity in $n-1$ gates of depth $\lceil \log n \rceil$ while the second needs $5(n-1)$ gates in the naive translation, and the best known constant-factor-optimal translation is not obviously tight. When a lower bound is stated for parity, the basis is part of the theorem, not an implementation detail.