Content deleted Content added
→References: include missing references |
→Key results: fix citation |
||
Line 26:
===Key results===
*The Boolean function [[parity function|PARITY]], which is 1 if and only if the sum of its input bits is odd, does not lie 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 (
* 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''−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<sup>0</sup>]] (Hesse 2001).
| |||