Content deleted Content added
Rescuing 1 sources and tagging 1 as dead.) #IABot (v2.0.9.5 |
m →Complexity classes: +wl |
||
Line 56:
==Complexity classes==
Many circuit complexity classes are defined in terms of class hierarchies. For each non-negative 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. The union NC of all of these classes is a subject to discussion. By considering unbounded fan-in gates, the classes [[AC (complexity)|AC<sup>i</sup>]] and AC (which is equal to NC) can be constructed. Many other circuit complexity classes with the same size and depth restrictions can be constructed by allowing different sets of gates.
==Relation to time complexity==
| |||