Content deleted Content added
m →References: added url to Håstad's thesis |
|||
Line 36:
Many circuit complexity classes are defined in terms of class hierarchies. For each nonnegative 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.
==See also==
*[[Transcomputational problem]]
==References==
| |||