We’d like to show that there exists an n-bit Boolean function that requires circuits of size \(\Omega(2^n/n)\).

The idea is to compare the number of n-bit Boolean functions \(f:\{0,1\}^n\to \{0,1\}\) to the number of small circuits (small will mean size \(s=2^n/100n\)).

Let us first count the number of n-bit Boolean functions. In general, the number of functions from a finite set X to a finite set Y is equal to \(|Y|^{|X|}\). (You should convince yourself of this fact.) Hence, in our case the number of n-bit Boolean functions is \(2^{2^n}\).

Now let’s count the number of size-s circuits. A circuit of size-s consists of a directed acyclic graph (DAG) on s vertices, each with in-degree at most 2. (The in-degree of a vertex is the number of arcs going into the vertex.) Furthermore, each source (in-degree 0) is labeled with an input variable \(x_i\). Each sink (out-degree 0) is labeled with an output variable \(y_j\). (We will assume there is only one sink, so that there is only one output bit. For the counting, it doesn’t really matter.) Each non-source/sink vertex is labeled with a Boolean function, either AND, OR, or NOT.

We claim that we can describe such a circuit completely by a bit string of length at most \(10s\log s\). First, we give every vertex a unique ID. Since there are only s vertices in the circuit, we only need log s bits for the ID. Our description of the circuit will consist of s pieces, each of length \(10\log s\) (one piece per vertex). To describe a single vertex u, we store the ID of u (\(\log s\) bits), the IDs of the vertices that have incoming arcs to u (\(2 \log s\) bits) and the label of u, which is either a Boolean function or the index of an input/output variable (at most log n bits). We don’t need to store the outgoing arcs of a vertex, because those will be stored as incoming arcs by other vertices. In total, we store at most \(3\log s + \log n\le 4\log s\) bits per vertex. Hence, the description of the whole circuit is indeed shorter than \(10s\log s\) bits.

It follows that the number of circuits of size s is at most \(2^{10 s\log s}\) (the number of bit strings of length \(10 s \log s\)). For \(s=2^n/100n\), this number is much less than \(2^{2^n}\). (Check this calculation.) It actually follows that an overwhelming majority of n-bit Boolean functions does not have circuits of size \(2^n/100n\).

As remarked in class, this bound is roughly tight up to the factor 100: Every n-bit Boolean function has a circuit of size \(100\cdot 2^n/n\).

What do these results mean? Unfortunately, they give very little information about how hard-to-compute functions look like. This lower bound essentially says that a random function has high circuit complexity. Why would we want to compute a particular random function? It’s a diffcult and important open question to show that an explicit, interesting functions has high circuit complexity (say, even super-linear size).