# AC^{0}

**AC ^{0}** 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

**NC**, which has only bounded-fanin AND and OR gates.

^{0}^{[1]}

## Example problems[edit]

Integer addition and subtraction are computable in AC^{0},^{[2]} but multiplication is not (at least, not under the usual binary or base-10 representations of integers).

## Descriptive complexity[edit]

From a descriptive complexity viewpoint, DLOGTIME-uniform AC^{0} is equal to the descriptive class FO+BIT of all languages describable in first-order logic with the addition of the BIT predicate, or alternatively by FO(+, ×), or by Turing machine in the logarithmic hierarchy.^{[3]}

## Separations[edit]

In 1984 Furst, Saxe, and Sipser showed that calculating the parity of an input cannot be decided by any AC^{0} circuits, even with non-uniformity.^{[4]}^{[1]}
It follows that AC^{0} is not equal to NC^{1}, because a family of circuits in the latter class can compute parity.^{[1]} More precise bounds follow from switching lemma. Using them, it has been shown that there is an oracle separation between the polynomial hierarchy and PSPACE.

## References[edit]

- ^
^{a}^{b}^{c}^{d}Arora, Sanjeev; Barak, Boaz (2009).*Computational complexity. A modern approach*. Cambridge University Press. pp. 117–118, 287. ISBN 978-0-521-42426-4. Zbl 1193.68112. **^**Barrington, David Mix; Maciel, Alexis (July 18, 2000). "Lecture 2: The Complexity of Some Problems" (PDF).*IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity*.**^**Immerman, N. (1999).*Descriptive Complexity*. Springer. p. 85.**^**Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomial-time hierarchy".*Mathematical Systems Theory*.**17**(1): 13–27. doi:10.1007/BF01744431. MR 0738749. Zbl 0534.94008.