Circuit complexity goes back to [[Claude Shannon|Shannon]] (1949), who proved that almost all Boolean functions on ''n'' variables require circuits of size Θ(2<sup>''n''</sup>/''n''). InDespite histhis 1999 book on circuit complexityfact, Vollmer states (pg. 1) that "the direction which ''complexity theoretictheorists researchwere onunable circuits''to tookprove wascircuit heavilylower influencedbounds by Savage's textbook",for citingspecific SavageBoolean 1976functions.
*The Booleanfirst function for which superpolynomial circuit lower bounds could be shown was the [[parity function|PARITY]], which is 1 if and only ifcomputes the sum of its input bits ismodulo odd,2. The fact that parity is not contained in [[AC0|AC<mathsup>AC^0</mathsup>. The result]] was first established independently by Ajtai (1983) and by Furst, Saxe and Sipser (1984). Later improvements by Håstad (1987) in fact establish that any family of constant-depth circuits computing PARITYthe parity function requires exponential size. Smolensky (1987) proved that this is true even if the circuit is augmented with gates computing the sum of its input bits modulo some odd prime p.▼
===Key results===
▲*The Boolean function [[parity function|PARITY]], which is 1 if and only if the sum of its input bits is odd, is not contained in <math>AC^0</math>. The result was first established independently by Ajtai (1983) and by Furst, Saxe and Sipser (1984). Later improvements by Håstad (1987) in fact establish that any family of constant-depth circuits computing PARITY requires exponential size. Smolensky (1987) proved that this is true even if the circuit is augmented with gates computing the sum of its input bits modulo some odd prime p.
* Consider theThe [[clique problem|''k''-clique problem]] ofis determiningto decide whether a given graph withon ''n'' vertices has a clique of size ''k''. For any particular choice of the constants ''n'' and ''k'', thisthe graph can be encoded asin abinary Booleanusing function<math>{n on\choose 2}</math> bits which indicate for each possible edge whether it is present. Then the ''nk''(''n''−1)-clique inputs,problem oneis forformalized eachas paira offunction vertices<math>f_k:\{0,1\}^{{n specifying\choose whether2}}\to\{0,1\}</math> or notsuch that edge<math>f_k</math> isoutputs in''1'' if and only if the graph encoded by the string contains a clique of size ''k''. This family of functions is monotone and can be computed by a family of circuits, but it has been shown that it cannot be computed by a polynomial-size family of monotone circuits (that is, circuits with AND and OR gates but nowithout negation). ThisThe original result of [[Alexander Razborov|Razborov]] (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). RazRossman (2008) shows that constant-depth circuits with AND, OR, and McKenzieNOT latergates showedrequire thatsize <math>\Omega(n^{k/4})</math> to solve the monotone''k''-clique NCproblem even in the [[average-case complexity|average case]]. Moreover, hierarchythere is infinitea circuit of size <math>n^{k/4+O(19991)}</math> which computes <math>f_k</math>.
*The Integer Division Problem lies in uniform [[TC0|TC<sup>0</sup>]] (Hesse 2001).▼
Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).
▲*The Integer Division Problem lies in uniform [[TC0|TC<sup>0</sup>]] (Hesse 2001).
