How many gates a truth table needs

A truth function of $n$ letters is a colouring of the corners of a cube, and one connective is enough to build any of them. The question the other measures of complexity circle — how sensitive a function is, how many letters a plane can separate — has a blunter form that engineers ask of every chip. How many gates does it take?

A circuit is a list of gates. Each gate takes two wires, each wire being either an input letter or the output of an earlier gate, and computes some operation of two truth values; the last gate’s output is the answer. Counting the gates of the smallest circuit measures the function’s cost. Allowing every operation of two inputs, rather than only one connective, changes each count by at most a constant factor — any two-input operation can be rebuilt from at most a handful of nand gates — and makes the numbers cleaner, so every operation is allowed except the six that ignore an input or return a constant — negation is kept, since it costs one step of the circuit.

The question has three answers at three scales. For three letters it can be settled completely by trying every circuit. For large $n$, counting settles how many gates almost every function needs, and a construction shows the count is right. And for any particular function that anyone can name, almost nothing is known, which is one of the central open problems of mathematics.

Four functions, four smallest circuits #

Parity — true when an odd number of letters are true — is two exclusive-or gates, and nothing less can do it, because one gate reads only two wires and the answer depends on all three letters. The selector needs three: one gate cannot combine three letters, two gates in every arrangement were tried and fail, and three succeed. Majority and exactly-one-true need four each.

Those minima are facts about all circuits, not about the ones a designer would think of, and the only way to establish them is to try every circuit smaller than the one found. With twelve operations and a growing number of wires to choose from, a four-gate circuit on three letters can be assembled in about 36 million ways, and a computer checks them all in a second. The circuit drawn is simply the first one the search found at the minimum size; others exist.

All of them, for three letters and for four #

For three letters the search reaches every one of the 256 functions within four gates, so the table is complete. The typical function needs two or three. No function of three letters needs five.

For four letters the same search, run to four gates, reaches only 13,624 of the 65,536 functions. The other 79 per cent need at least five. Carrying the search further by brute force becomes expensive quickly, and Donald Knuth completed the computation for four letters by grouping the functions into 222 kinds that relabelling and negation cannot tell apart and searching cleverly within each; by his count the hardest functions of four letters need seven gates.

That already shows the pattern. At three letters the typical function is cheap; at four it is not, and the fraction of functions that fit into any fixed number of gates collapses as letters are added. The number of functions, $2^{2^n}$, doubles its exponent with each new letter, while the number of small circuits grows far more slowly.

The hardest functions of three letters #

The hardest functions of three letters are not the ones with the most complicated formulas. Parity has the longest formula in and-or-not form and needs only two gates, because exclusive-or is available. The hard ones are majority and its relatives, and “exactly one true” and its relatives.

On the cube, majority is the set of corners with at least two true letters — the corners on one side of a plane, a weighted vote with equal weights. Exactly-one-true is the three corners adjacent to the all-false corner. Neither is built by a short chain of the available operations, and the search shows that each needs a fourth gate to combine partial answers that no pair of letters provides alone. The sorting uses the 48 ways of renaming and negating three letters and the 2 ways of negating the answer, and under them the 256 functions of three letters fall into 14 kinds. A circuit for one member of a kind becomes a circuit for any other by relabelling its inputs and swapping each gate for the operation that absorbs the negations, so the count is the same across a kind and the search needs to be believed only once for each. Both hardest kinds were checked member by member all the same.

That is a fact about three letters, and it does not predict which functions are hardest at larger sizes; what it does illustrate is that “hard” here means something that the formula written on the page does not show.

Formulas against circuits #

A circuit may use a gate’s output more than once, and that is what separates it from a formula. A formula written in the usual way is a tree: every intermediate result feeds exactly one later operation, so a value needed twice must be computed twice. The map that puts neighbours side by side found the shortest two-level formula for a function by covering its true corners with rectangles, and even the best such cover pays for every shared piece separately.

The difference is not small. Parity of $n$ letters is a chain of $n - 1$ exclusive-or gates as a circuit. Written as a formula in “and”, “or” and “not”, it needs about $n^2$ symbols at the least, which Valeriy Khrapchenko proved in 1971, and in the two-level form of a Karnaugh map it needs $2^{n-1}$ terms, one for every odd corner. The counting argument for formulas also gives a different threshold: since a formula is a tree, formulas of a given size are fewer than circuits of the same size, and almost every function needs a formula of about $2^n/\log_2 n$ symbols rather than $2^n/n$ gates.

Sharing is also what makes the constructions below efficient. Every construction that approaches the count does so by computing some pieces once and routing them to many places, which is something a formula cannot do and a circuit does for free.

Shannon’s count #

Claude Shannon turned the pattern into a theorem in 1949, by counting, and what counting can prove exists gives the argument in a line. The figure makes the line into numbers. A circuit of $s$ gates on $n$ letters is described by choosing, for each gate in turn, one of twelve operations and two of the wires before it; the number of such descriptions is at most a product that grows like $(s^2)^s$. A function with no circuit of $s$ gates must exist as long as that number is below $2^{2^n}$, the number of functions. For twenty letters the number of functions is $2^{1{,}048{,}576}$, and circuits do not become that numerous until they have 35,061 gates.

Where the $n$ in the denominator comes from is visible in the arithmetic. The logarithm of the number of circuits of $s$ gates is about $2s\log_2 s$, since each gate chooses two wires from about $s$ of them. Setting that equal to the logarithm of the number of functions, $2^n$, gives $s \log_2 s \approx 2^{n-1}$, and since $\log_2 s$ is then close to $n$, the solution is $s \approx 2^{n-1}/n$. The logarithm of the circuit count carries a factor of $\log s$ that the logarithm of the function count does not, and that factor is the $n$.

The threshold grows like $2^n/n$. Doubling the number of circuits per gate, or counting circuits more cleverly, changes the constant in front and not the shape. And the argument says more than that some function is hard: the circuits of fewer gates than the threshold compute a vanishing fraction of the functions, so a function chosen at random is almost certainly near the maximum. Almost every function of $n$ letters needs about $2^n/n$ gates.

Enough gates for every function #

A lower bound for almost every function asks for an upper bound for every function, and three constructions give one of increasing quality.

The first is the one every textbook gives: for each row where the function is true, one “and” of $n$ literals, then one big “or” of the terms. That costs about $n \cdot 2^n$ gates, a factor of $n^2$ too many. The second uses the selector of the first figure: split on the first letter, building the function for each of its two values, and choose between them — which costs three gates per split, and about $3 \cdot 2^n$ in all.

The third is David Muller’s idea of 1956, and it is where the factor of $n$ is won back. Choose a small number $k$ and build, once, every one of the $2^{2^k}$ functions of the last $k$ letters. Then the selector tree only needs to split on the first $n - k$ letters, and each of its $2^{n-k}$ leaves is a wire into the shared table rather than a subcircuit of its own. With $k$ about $\log_2 n$, the table costs little and the tree costs $2^n/n$ times a constant. Lupanov refined the idea in 1958 until the constant was one: every function of $n$ letters can be built with $(1 + o(1))\,2^n/n$ gates. The hardest function of $n$ letters needs almost exactly $2^n/n$ gates, and almost every function is nearly that hard.

Naming a hard function #

Now ask for one. A function defined by a short rule — the parity of the number of cliques in a graph written out in the letters, the answer to “does this formula have a satisfying assignment”, anything whose truth table a program can print — which is proved to need many gates. The counting argument cannot provide one, because it does not name the functions it proves exist, and nothing else has come close.

The best lower bound known for any explicit function is a small multiple of $n$. Schnorr proved $2n$ in 1974; Wolfgang Paul $2.5n$ in 1977; Norbert Blum $3n$ in 1984; Magnus Find, Alexander Golovnev, Edward Hirsch and Alexander Kulikov $(3 + \tfrac{1}{86})n$ in 2016; Li and Yang $3.1n$ in 2022. Fifty years of work have moved the constant from two to a little over three, while the functions nobody can name need a number of gates exponential in $n$.

All of these proofs work the same way, by gate elimination. Fix one input letter to a constant; the circuit’s gates that read it simplify, and at least a few of them disappear entirely. The function that remains is a function of one letter fewer, chosen so that it is still of the same hard type, and the argument repeats. If each fixing removes at least three gates, a function of $n$ letters needs at least $3n$ gates. The improvements since 1984 are improvements in the bookkeeping — showing that on average slightly more than three gates vanish — and there are known reasons why the method, on its own, cannot go much further than a small constant times $n$.

The difficulty is not a lack of candidates. If some function whose truth can be checked quickly — a problem in the class NP, such as the satisfiability of a set of clauses — needs circuits larger than every polynomial in $n$, then NP problems cannot all be solved in polynomial time, which would settle the question of P against NP. Proving an explicit lower bound even of $5n$ is therefore a small step toward the largest open problem in the theory of computation, and the obstacles to taking it are well mapped. Alexander Razborov and Steven Rudich showed in 1994 that a large class of natural proof strategies, the kind that work by identifying a property most functions have and a small circuit cannot, would also break widely believed cryptographic assumptions, and so cannot succeed if those assumptions hold.

What is known with restrictions #

Strong lower bounds do exist when the circuits are restricted. Circuits with only “and” and “or” gates — no negation — are called monotone, and Razborov proved in 1985 that detecting a clique of a given size in a graph needs monotone circuits of more than polynomial size, and Noga Alon and Ravi Boppana pushed the bound to exponential in 1987. Circuits of constant depth with unlimited fan-in cannot compute parity unless they are exponentially large, as Merrick Furst, James Saxe and Michael Sipser, and independently Miklós Ajtai, showed in the early 1980s and Johan Håstad sharpened in 1986. And formulas, circuits in which every gate’s output is used once, have explicit lower bounds of about $n^3$, due to Andreev and to Håstad.

Each restriction removes something the general circuit uses. Monotone circuits cannot cancel, constant-depth circuits cannot iterate, and formulas cannot reuse a computed value — which is exactly what Muller’s shared table and Lupanov’s construction rely on. The general case has none of these handholds, and on it the counting argument stands alone.

What the figures cannot show #

The exact counts for three letters are complete: every circuit of up to four gates was tried, and every function was reached. For four letters the search stops at four gates, and the 51,912 functions it does not reach are known to need at least five; the exact figures beyond that, including the maximum of seven, come from Knuth’s computation rather than from the search drawn here.

The counting threshold uses a simple overestimate of the number of circuits — it counts some circuits several times, since gates can often be listed in more than one order — and a sharper count would move each point by a constant factor without changing the $2^n/n$ shape. The constructions’ gate counts are computed from their recipes, not from built circuits; they are upper bounds that the recipes guarantee.

And a circuit’s size is one measure among several. Depth, the longest chain of gates from input to output, measures how long a computation takes when gates work in parallel, and it has its own counting argument, its own constructions and its own gap between what most functions need and what can be proved for named ones.

Still open: a named function that needs many gates #

No function in NP is known to need more than $3.1n$ gates. The conjecture that some NP function needs more than any polynomial is widely believed and would imply that P is not NP; the weaker statement that some needs $5n$, or $10n$, is also unproved. Even for functions in much larger classes — computable in exponential time, with the ability to guess — superpolynomial circuit lower bounds are not known, and the frontier there is also set by barriers like Razborov and Rudich’s.

At the small end the open questions are concrete. The exact circuit sizes of all functions of five letters have not been computed in full; the search space is too large for the methods that settled four, and the largest number of gates a function of five letters can need is not known. A table that is complete for three letters and for four stops at the next size, which is the whole difficulty of the subject in miniature: the functions are finite, the circuits are finite, and the numbers outrun every method long before they outrun the question.

An abundance that cannot be pointed to #

Almost every truth function is as hard as a function can be. A random function of three hundred letters needs more gates than there are atoms in the observable universe, and that is a theorem. Yet no function anyone can describe is known to need more than a few hundred.

The two facts are consistent because the counting argument is non-constructive in exactly the way what counting can prove exists describes: it shows the small circuits are too few to go round, and says nothing about which functions are left out. Every function that can be named has a short description, and it is precisely among the functions with short descriptions that a small circuit might be hiding. The hard functions are everywhere, and the ones that can be pointed to are, as far as anyone can prove, easy.