Circuit complexity: Difference between revisions

Revision as of 17:48, 29 March 2011

Revision as of 17:51, 29 March 2011

Line 23:

==History==

Circuit complexity goes back to [[Claude Shannon|Shannon]] (1949), who proved that randomalmost all Boolean functions withon ''n'' inputsvariables require circuits of size Θ(2^''n''/''n''). In his 1999 book on circuit complexity, Vollmer states (pg. 1) that "the direction which ''complexity theoretic research on circuits'' took was heavily influenced by Savage's textbook", citing Savage 1976.

===Key results===

*The Boolean function [[parity function|PARITY]], which is 1 if and only if the sum of its input bits is odd, doesis not liecontained 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 the [[clique problem]] of determining whether a graph with ''n'' vertices has a clique of size ''k''. For any particular choice of ''n'' and ''k'' this can be encoded as a Boolean function on ''n''(''n''&minus;1) inputs, one for each pair of vertices, specifying whether or not that edge is in the graph. 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 no negation). This original result of [[Alexander Razborov|Razborov]] (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).

*The Integer Division Problem lies in uniform [[TC0|TC⁰]] (Hesse 2001).