Boolean Circuits · Lower Bounds
Lesson 2
Below, we will prove exact bounds on the circuit complexity of the parity function in two different bases. Note that exact bounds are quite rare: for many other functions, we can only prove very weak lower bounds (for example, \(n\) or \(2n\)), while the known upper bounds can be either polynomial (say, \(n^{3}\)) or even exponential (for example, \(2^{\sqrt n}\)).
Theorem (Schnorr, 1974). Let \(U_{2} = B_{2} \setminus \{\oplus, \equiv\}\). Then \[C_{B_2}(\oplus_{n}) = n - 1 \quad \text{and}\quad C_{U_2}(\oplus_{n}) = 3(n - 1) \ .\]
Proof.
- Base \(B_{2}\).
- Upper bound. Any tree with leaves \(x_{1}, \dotsc, x_{n}\) and each internal gate computing the function \(\oplus\) will suffice.
- Lower bound. Roughly, the proof is done by counting wires in the circuit. The parity function depends essentially on all its variables. This means that each input gate has at least one wire coming out. Furthermore, each gate, except the output gate, takes two wires as input and produces at least one wire as output—thus, it reduces the number of dangling wires by at most one. Therefore, at least \((n - 1)\) gates are required.
- Base \(U_{2}\).
- Upper bound. Three gates in the \(U_{2}\) basis can compute the parity function of two bits \(x_{1}\) and \(x_{2}\) as follows: \(x_{1} \oplus x_{2} = (x_{1} < x_{2}) \lor (x_{1} > x_{2})\). Similarly, three additional gates can be used to add another variable. In total, this gives \(3(n - 1)\).
- Lower bound. We will prove the lower bound for the circuit complexity of the parity function and its negation by induction on \(n\). In other words, we will prove a slightly stronger statement: for any \(n \in \mathbb{Z}_{\ge 1}\) and any \(c \in \{0, 1\}\), we have \[C_{U_2}(x_{1} \oplus x_{2} \oplus \dotsb \oplus x_{n} \oplus c) \ge 3(n - 1) \ .\]
The base case \(n = 1\) is obvious. Now assume \(n > 1\). Consider an optimal circuit and any topological ordering of its gates. Let \(A\) be the first gate in this sorting, and suppose it depends on variables \(x_{i}\) and \(x_{j}\). It is easy to see that \(i \neq j\) (otherwise, \(A\) would compute \(x_{i}\) or \(x_{i} \oplus 1\) and could be removed from the circuit).
Now we need to use the function that \(A\) can compute. To do this, we classify all 16 functions \(f(x, y)\) in \(B_{2}\):- Two xor-functions: \(x \oplus y \oplus a\), where \(a \in \{0,1\}\).
- Eight and-functions: \((x \oplus a) \land (y \oplus b) \oplus c\), where \(a,b,c \in \{0,1\}\).
- Four degenerate functions: \(x\), \(x \oplus 1\), \(y\), \(y \oplus 1\).
- Two constants: 0 and 1.
From this, we conclude that both \(x_{i}\) and \(x_{j}\) must have another outgoing wire besides their wire to \(A\). Indeed, suppose there is no other wire coming from \(x_{i}\). Then substituting \(x_{j} \gets b\) makes gate \(A\) constant (it would compute the constant \(c\)), and the circuit would no longer depend on \(x_{i}\). But after substituting \(x_{j} \gets b\), the parity function must compute either the parity of all remaining variables, or its negation.
So, we know that there are two wires coming out of \(x_{i}\). Let the second gate be \(B\). Our plan is as follows: we will substitute a constant into \(x_{i}\) to remove at least three gates. After that, we will have the parity function (or its negation) of \(n - 1\) variables and can apply the induction hypothesis. To remove three gates, we make the substitution \(x_{i} \gets a\). Gate \(B\) will be removed, and gate \(A\) will compute a constant, thus removing itself and at least one of its descendants (gate \(A\) cannot be an output gate, because otherwise the substitution \(x_{i} \gets a\) would make the whole circuit constant, which does not happen when \(n > 1\)). If \(B\) was the only descendant of \(A\), then \(B\) will become constant, and its descendant will also be removed.
◼