Also known as AC⁰
thumbnail|Diagram of an AC0 circuit: The n input bits are on the bottom and the top gate produces the output; the circuit consists of AND- and OR-gates of polynomial fan-in each, and the alternation depth is bounded by a constant.
Wikidata facts
Show 1 more fact
- Stack Exchange tag
- cstheory.stackexchange.com/tags/ac0
Sources (1)
via Wikidata · CC0
~3 min read
Article
4 sectionsContents
- Example problems
- Descriptive complexity
- Separations
- References
thumbnail|Diagram of an AC0 circuit: The n input bits are on the bottom and the top gate produces the output; the circuit consists of AND- and OR-gates of polynomial fan-in each, and the alternation depth is bounded by a constant.
AC0 (alternating circuit) is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-fanin AND gates and OR gates (we allow NOT gates only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates. Such circuits are called "alternating circuits", since it is only necessary for the layers to alternate between all-AND and all-OR, since one AND after another AND is equivalent to a single AND, and the same for OR.