Boolean Circuits · Maximum Complexity

Lesson 7

Nikolai Chukhin · Alexander S. Kulikov

Now everything is ready for the proof of the theorem!

Proof. Any function \(f \in B_{n}\) can be “decomposed” according to the first \(k\) variables: \[f(x_{1}, \dotsc, x_{n})=\bigvee_{a \in \{0,1\}^k}[x_{1}=a_{1}, \dotsc, x_{k}=a_{k}] \land g_{a}(x_{k+1}, \dotsc, x_{n}) \ .\] Here \([x_{1}=a_{1}, \dotsc, x_{k}=a_{k}] \in B_{k}\) is a function that takes the value 1 only when the condition inside the parentheses is satisfied, and \(g_{a}\) is the function obtained from \(f\) by substituting constants from \(a\) in place of the first \(k\) variables. Using this decomposition, we can compute \(f\) as follows:

  1. Compute all monomials over \(x_{1}, \dotsc, x_{k}\). This requires \(O(2^{k})\) gates.
  2. After that, compute all functions from \(n-k\) variables. This takes \(O(2^{2^{n-k}})\) gates.
  3. Finally, use the decomposition to compute the function \(f\). This step requires \(2 \cdot 2^{k}-1\) gates: first, compute the conjunction of each monomial with the corresponding function of \(n-k\) variables (\(2^{k}\) gates), and then compute the disjunction of all these \(2^{k}\) conjunctions (\(2^{k}-1\) gates).
The resulting circuit has size \[O\left(2^{k}+2^{2^{n-k}}\right) \ .\] Now, set \(k=n-\log(n - \log n)\). The resulting estimate then becomes \(O(2^{n}/n)\).◼

For the curious 🤓
In 1958, Oleg Borisovich Lupanov proved that the constant in \(O(\cdot)\) is equal to one: any function \(f \in B_{n}\) can be computed by a circuit of size \((1+o(1))2^{n}/n\).