Content deleted Content added
→Size and depth: Made the article easier to skim by bolding the definitions of circuit size and depth. |
m →Complexity classes: add unsourced section template |
||
Line 56:
==Complexity classes==
{{Unreferenced section|date=October 2024}}
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.
| |||