The Counting Argument for Circuit Size Lower Bounds

Shannon’s 1949 paper on switching circuits contains a bound that has not been improved in any essential way since: almost every Boolean function on $n$ variables requires a circuit with at least $2^n/n$ gates, up to lower-order terms. The proof takes half a page. Its conclusion is simultaneously the strongest general lower bound known and the least useful one, because it says nothing about which functions are hard. Understanding why requires counting circuits rather than analysing them.

Two counts that must be compared

The argument compares the number of functions to the number of small circuits. If the second is smaller, some function is left without a small circuit.

There are $2^{2^n}$ Boolean functions on $n$ variables, since a function is a table of $2^n$ output bits and each bit is free.

Now count circuits of size at most $s$ over a fixed complete basis, say fan-in-two ${\wedge, \vee, \neg}$ with inputs among $x_1, \ldots, x_n$. Specify a circuit by listing its gates in topological order. For gate $i$, choose one of three types and two input wires from the $n + i - 1$ wires available at that point. The number of choices at step $i$ is at most $3(n+i)^2$, so the total is at most

$$\prod_{i=1}^{s} 3(n+i)^2 \le \left(3(n+s)^2\right)^{s}.$$

Setting this below $2^{2^n}$ and solving gives $s = \Theta(2^n/n)$: a circuit of that size has fewer than $2^{2^n}$ descriptions, so at least one function has no circuit that small. The exact constant depends on the basis and on how generously descriptions are counted, but the exponent does not.

The bound is not merely existential about one function. Divide the number of small circuits by the number of functions and the fraction tends to zero, so the set of functions computable with, say, $0.9 \cdot 2^n/n$ gates is a vanishing fraction of all functions. A randomly chosen truth table is hard with probability tending to one, and its hardness is a statement about the table, not about any structure inside it.

Matching from above

A lower bound is only half a result. Lupanov supplied the other half: every Boolean function on $n$ variables has a circuit of size at most $2^n/n \cdot (1 + o(1))$ in the same basis. Together the two bounds pin the worst-case circuit complexity of an $n$-variable function to within a factor approaching one, and they are among the very few places in complexity theory where upper and lower bounds meet.

The construction decomposes the truth table into blocks. Split the $n$ inputs into a group of $k$ and a group of $n-k$. For each of the $2^{n-k}$ assignments to the second group, the function restricts to a function of $k$ variables, and that restricted function can be written as a disjunction of at most $2^k$ minterms. Choosing $k$ near $\log n$ balances the two costs: the minterms are cheap to build because they are short, and the number of blocks is large but each block shares its decoder. The optimisation over $k$ produces the $2^n/n$ coefficient.

# Upper bound shape, not the optimal construction: a truth-table lookup built
# from a binary decoder plus one AND per accepting minterm.
def lookup_circuit_size(n, accepting):
    """Gates needed for the naive DNF: n inverters, 2^n minterms of n-1 ANDs,
    and one OR over the accepting minterms."""
    inverters = n
    minterm_cost = max(n - 1, 0)
    ands = (1 << n) * minterm_cost
    ors = max(len(accepting) - 1, 0)
    return inverters + ands + ors

# The naive DNF is Theta(n * 2^n). Lupanov's block decomposition removes the
# factor of n by sharing sub-minterms across blocks.

The naive DNF costs $\Theta(n 2^n)$, a factor of $n$ above optimal. The saving comes entirely from sharing: the same short minterm appears in many blocks, and a decoder built once serves all of them. This is the same economy that makes a ROM cheaper than a pile of separate lookup tables.

Why the argument cannot be cashed in

The counting bound establishes that hard functions exist without exhibiting one, and the gap between “exists” and “here it is” is the central difficulty of the field.

The reason is that a counting argument is blind to structure. It bounds the number of circuits by bounding the number of descriptions, and every description is treated as equally likely. Any proof that a specific function $f$ needs more than $c n$ gates must use something about $f$ — its symmetry, its algebraic degree, its behaviour under restrictions — because the generic count applies equally to all functions and therefore cannot distinguish $f$ from a function that happens to have a small circuit.

There is a second, sharper obstruction. A proof that establishes a lower bound by a property shared by almost all functions, checkable in polynomial time on the truth table, and not shared by functions with small circuits, is exactly the shape of a natural proof, and such proofs cannot separate $\mathrm{P}$ from $\mathrm{NP}$ unless factoring and similar problems are easy. The natural proofs barrier develops that argument; the counting bound itself is the archetype of a property that is large and constructive but not efficiently checkable, which is why it escapes the barrier and why it also cannot be turned into an explicit result.

The numbers, stated honestly

For unrestricted circuits over a complete basis, the best lower bound for a function in $\mathrm{NP}$ is not $2^n/n$ but linear. The strongest explicit bound known is $3.1n - o(n)$ gates, proved by Find, Golovnev, Hirsch and Kulikov in 2016 for a function in $\mathrm{P}$; earlier work by Iwama and Morizumi and by Lachish and Raz established bounds of the same linear shape with larger constants. Every one of these is a statement about the full basis with no depth restriction, and every one is far below the counting bound.

The gap has a precise interpretation. Counting says the hard functions are dense; explicit methods can only analyse functions whose structure they can describe. Between those two facts sits the entire programme of restricted-model lower bounds: fix a structural restriction strong enough that a combinatorial argument works, prove a bound inside the restriction, and then try to remove the restriction. The switching lemma is the most successful instance, and it succeeds precisely because it restricts depth rather than size.

What the bound does establish

Three things survive and are used constantly.

Worst-case circuit complexity is not subexponential in the input length for general functions. Any claim that a technique computes arbitrary Boolean functions in size $o(2^n/n)$ is false, and this rules out a family of hoped-for general-purpose compression schemes for truth tables.

The bound is basis-independent up to constants, since the conversion between complete bases costs only a constant factor. A lower bound of $2^n/n$ in one complete basis implies $\Omega(2^n/n)$ in any other.

The bound is tight for the worst case, which means the interesting question is never “how large can a circuit be” but “which functions are smaller than the worst case, and by how much”. That reframing is what makes the polynomial-size class $\mathrm{P/poly}$ meaningful: it selects the functions that are exponentially below the counting bound, and the non-uniform model is the framework in which that selection is studied.

A note on the encoding

The count above charges each gate for its type and its two input wires, and it ignores the possibility that different descriptions denote the same circuit. Both choices are generous to the lower bound: a description may be redundant, so the number of distinct circuits of size $s$ is at most the number of descriptions, which is what the argument needs. If circuits were counted exactly, the bound would improve by a constant factor at most.

The count also assumes gates have fan-in two. With unbounded fan-in, a gate must specify a type and a subset of preceding wires rather than a pair, so the number of choices per gate grows from about $(n+i)^2$ to about $2^{n+i}$, and the same balance against $2^{2^n}$ still gives the $\Theta(2^n/n)$ conclusion with a smaller constant in the exponent. Depth-restricted counting is different in kind: a depth-$d$ circuit of size $s$ has at most $s^d$ descriptions up to relabelling, and that smaller count is what makes the depth hierarchy provable at the bottom levels while the size hierarchy remains open.