AC<sup>0</sup> (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 NC<sup>0</sup>, 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.
Integer addition and subtraction are computable in AC<sup>0</sup>, but multiplication is not (specifically, when the inputs are two integers under the usual binary or base-10 representations of integers).
Since it is a circuit class, like P/poly, AC<sup>0</sup> also contains every unary language.
From a descriptive complexity viewpoint, DLOGTIME-uniform AC<sup>0</sup> 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.
In 1984 Furst, Saxe, and Sipser showed that calculating the PARITY of the input bits (unlike the aforementioned addition/subtraction problems above which had two inputs) cannot be decided by any AC<sup>0</sup> circuits, even with non-uniformity. Similarly, computing the majority is also not in . It follows that AC<sup>0</sup> is strictly smaller than TC<sup>0</sup>. Note that "PARITY" is also called "XOR" in the literature.
However, PARITY is only barely out of AC<sup>0</sup>, in the sense that for any , there exists a family of alternating circuits using depth and size . In particular, setting to be a large constant, then there exists a family of alternating circuits using depth , and size only slightly superlinear.
can be divided further, into a hierarchy of languages requiring up to 1 layer, 2 layers, etc. Let be the class of languages decidable by a threshold circuit family of up to depth :The following problem is -complete under a uniformity condition. Given a grid graph of polynomial length and width , decide whether a given pair of vertices are connected.
The addition of two -bit integers is in but not in .