Lesson 5

To prove the theorem, we will need two auxiliary lemmas.

Lemma. All functions from \(B_{k}\) can be computed by a circuit of size at most \(O(|B_{k}|)=O(2^{2^k})\).

Proof. We will prove this by induction on \(k\). First, we compute all functions of \((k-1)\) variables. After that, we can compute any function of \(k\) variables using two additional gates: \[f(x_{1}, \dotsc, x_{k})=x_{k} \land g(x_{1}, \dotsc, x_{k-1}) \oplus h(x_{1}, \dotsc, x_{k-1}) \ .\] In total, we will use \(c2^{2^{k-1}}+2 \cdot 2^{2^k}\). Clearly, we can choose a constant \(c\) so that this is no more than \(c2^{2^k}\).◼