Consider the following Boolean valued function on $n$ Boolean variables: $f(x_{1},\dots,x_{n}) = x_{1} + \dots + x_{n}(\text{mod } 2)$, where addition is over integers, mapping $\textbf{‘FALSE’}$ to $0$ and $\textbf{‘TRUE’}$ to $1.$ Consider Boolean circuits (with no feedback) that use only logical $\textbf{AND}$ and $\textbf{OR}$ gates, and where each gate has two input bits, each of which is either an input bit of $f$ or the output bit of some other gate of the circuit. The circuit has a distinguished gate whose value is the output of the circuit. The minimum size of such a circuit computing $f$ (asymptotically in $n$) is :
- $2^{o(\log n)}$
- $n^{c}$, for some fixed constant $c$
- $n^{\omega(1)}$, but $n^{O(\log n)}$
- $2^{\Theta(n)}$
- None of the others
