Lesson 2

Let's start by proving the lower bound on the maximum complexity: \(S(n)=\Omega(2^{n}/n)\). This means that there are functions that cannot be computed by circuits of size \(o(2^{n}/n)\). Moreover, as the following theorem shows, there are many such functions. In fact, almost all Boolean functions have this property.

Theorem (Shannon, 1949). The circuit complexity of almost all Boolean functions from \(B_{n}\) is at least \(\Omega(2^{n}/n)\) (in other words, the ratio of such functions is \(1-o(1)\)).

Proof. This is proven by counting: we will show that there is not enough small circuits to compute all \(|B_{n}|=2^{2^n}\) functions.

We will estimate the number \(s(n,r)\) of circuits with \(n\) inputs and \(r\) gates. To define such a circuit, for each of the \(r\) gates, we need to choose one of 16 functions that it computes, and also specify which gates or inputs the wires come from: \[s(n,r) \le \left(16\cdot (n+r)^{2}\right)^{r} \ .\] Now set \(r=\alpha \cdot \frac{2^n}{n}\), where \(\alpha\) is a constant that we will choose later, and estimate this expression from above. Assume \(n\) is sufficiently large. This allows us to write \(n+\alpha \frac{2^n}{n}\le 2\alpha \frac{2^n}{n}\).

\[\begin{align*}s\left(n, \alpha\frac{2^n}{n}\right)&\le \left(16 \cdot \left(2 \alpha \cdot \frac{2^n}{n}\right)^{2}\right)^{\alpha \frac{2^n}{n}}&\text{(upper bound for \(s(n, r)\))}\\&= \left(2^{2\cdot(n-\log_2 n + 3 +\log_2 \alpha)}\right)^{\alpha \frac{2^n}{n}}\\&= 2^{2^n\cdot\left(\frac{2\alpha \cdot(n-\log_2 n + 3 +\log_2 \alpha)}{n}\right)}\ .\end{align*}\]

The fraction inside the parentheses approaches \(2\alpha\) as \(n\) grows. Therefore, for \(\alpha=\frac{1}{3}\) (and sufficiently large \(n\)), the exponent will be much smaller than \(2^{n}\). This already shows that circuits of size \(\alpha \cdot \frac{2^n}{n}\) are insufficient to compute all \(2^{2^n}\) functions. Moreover, a randomly selected function from \(B_{n}\) will have circuit complexity above \(\alpha \cdot \frac{2^n}{n}\) with probability \(1-\frac{1}{2^{c2^n}}\).◼