Content deleted Content added
added some of the key results. |
+description of hierarchies. |
||
Line 19:
*The monotone function CLIQUE 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).
*Division lies in uniform [[TC0]] (Hesse 2001).
==Complexity classes==
Many circuit complexity classes are defined in terms of class hierarchies. For each integer ''i'', there is a class [[NC (complexity)|NC<sup>i</sup>]], consisting of polynomial-size circuits of depth <math>O(\log^i(n))</math>, using bounded fan-in AND, OR, and NOT gates. We can talk about the union NC of all of these classes. By considering unbounded fan-in gates, we construct the classes [[AC (complexity)|AC<sup>i</sup>]] and AC. We construct many other circuit complexity classes with the same size and depth restrictions by allowing different sets of gates.
==References==
| |||