Shannon's counting argument for circuit size

Remarks

The proof counts circuits. A circuit with $t \le s$ gates is described by giving, for each gate, its type among three and its at most two inputs. These inputs are chosen among the $n + t$ inputs and gates, and the last gate is the output. So there are at most $(s + 1)\big(3 (n + s)^2\big)^{s}$ circuits with at most $s$ gates. For $s = 2^n / (10 n)$ and large $n$, one has $n + s \le 2^n$, so the logarithm in base $2$ of this number is at most $s (2n + 2) + \log_2(s + 1) \le 2^n / 4$. So at most $2^{2^n / 4}$ functions have circuits of size $s$, out of $2^{2^n}$ functions.

The bound is sharp up to a constant: Lupanov showed that every function in $F_n$ has circuit size $O(2^n / n)$. The argument proves that hard functions exist but does not name one.

Going deeper

For a student

Claude Shannon gave the counting argument in 1949, in his work on switching circuits. It is a model for many existence proofs in complexity theory. It also shows that the class P/poly does not contain all languages. The gap between this lower bound for random functions and the linear lower bounds known for explicit functions is the central difficulty of circuit complexity.