AC0

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 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).[1] It thus contains NC0, which has only bounded-fanin AND and OR gates.[1]

  1. ^ a b Cite error: The named reference AB was invoked but never defined (see the help page).