Lesson 4

Now we will establish that any function of \(n\) variables can be computed by a circuit of size \(O(2^{n}/n)\). This immediately implies that \(S(n)=\Theta(2^{n}/n)\).

Theorem (Müller, 1956). Any function from \(B_{n}\) can be computed by a circuit of size \(O(2^{n}/n)\).