Content deleted Content added
Hatifnatter (talk | contribs) |
|||
Line 55:
==Complexity classes==
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 (which is equal to NC). We may construct many other circuit complexity classes with the same size and depth restrictions by allowing different sets of gates.
==Relation to time complexity==
| |||