AC0

AC⁰ is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all 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 NC⁰, which has only bounded-fanin AND and OR gates.

From a descriptive complexity viewpoint, DLOGTIME-uniform AC⁰ is equal to the descriptive class FO+BIT of all languages describable in first-order logic with the addition of the BIT operator, or alternatively by FO(+, $imes$).

In 1984 Furst, Saxe, and Sipser showed that calculating the parity of an input cannot be decided by any AC⁰ circuits, even with non-uniformity. [M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. "Math. Systems Theory", 17:13–27, 1984.] This leads us to a proof that AC⁰ is not equal to NC¹ Fact|date=February 2007.

References