 Then applying the probabilistic method, for sufficiently large formula_8, we know there is some formula_5 for which

Plugging in formula_33, we see that formula_34.Thus we have proven that the smallest circuit to compute the parity of formula_8 variables using only formula_36 must use at least this many variables.Although this is not an exceptionally strong lower bound, random restrictions have become an essential tool in complexity.