AC⁰ (alternating circuit) is acomplexity class used incircuit complexity. It is the smallest class in theAC hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-faninAND gates andOR gates (we allowNOT gates only at the inputs).^[1] It thus containsNC⁰, which has only bounded-fanin AND and OR gates.^[1] 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⁰,^[2] but multiplication is not (specifically, when the inputs are two integers under the usual binary^[3] or base-10 representations of integers).

Since it is a circuit class, likeP/poly, AC⁰ also contains everyunary language.

From adescriptive complexity viewpoint,DLOGTIME-uniform AC⁰ is equal to the descriptive classFO+BIT of alllanguages describable in first-order logic with the addition of theBIT predicate, or alternatively by FO(+, ×), or byTuring machine in thelogarithmic hierarchy.^[4]

In 1984 Furst, Saxe, andSipser showed that calculating thePARITY of the input bits (unlike the aforementioned addition/subtraction problems above which had two inputs) cannot be decided by any AC⁰ circuits, even with non-uniformity. Similarly, computing the majority is also not in${\displaystyle {\mathsf{A}\mathsf{C}}^0}$.^[5][1]It follows that AC⁰ is strictly smaller thanTC⁰. Note that "PARITY" is also called "XOR" in the literature.

However, PARITY is only barely out of AC⁰, in the sense that for any${\displaystyle k>0}$, there exists a family of alternating circuits using depth${\displaystyle \lceil k\ln n/\ln \ln n\rceil }$ and size${\displaystyle O\left(2^{(\ln n{)}^{1/k}}\frac{n}{(\ln n{)}^{1/k}}\right)}$.^[6]: 135 In particular, setting${\displaystyle k}$ to be a large constant, then there exists a family of alternating circuits using depth${\displaystyle O(\ln n/\ln \ln n)\ll O(\ln n)}$, and size only slightly superlinear.

${\displaystyle {\mathsf{A}\mathsf{C}}^0}$ can be divided further, into a hierarchy of languages requiring up to 1 layer, 2 layers, etc. Let${\displaystyle {\mathsf{A}\mathsf{C}}_d^0}$ be the class of languages decidable by a threshold circuit family of up to depth${\displaystyle d}$:$${\displaystyle {\mathsf{A}\mathsf{C}}_1^0\subset {\mathsf{A}\mathsf{C}}_2^0\subset \cdots \subset {\mathsf{A}\mathsf{C}}^0=\bigcup _{d=1}^{\mathrm{\infty }}{\mathsf{A}\mathsf{C}}_d^0}$$The following problem is${\displaystyle {\mathsf{A}\mathsf{C}}_d^0}$-complete under a uniformity condition. Given a grid graph of polynomial length and width${\displaystyle k}$, decide whether a given pair of vertices are connected.^[7]

The addition of two${\displaystyle n}$-bit integers is in${\displaystyle {\mathsf{A}\mathsf{C}}_3^0}$ but not in${\displaystyle {\mathsf{A}\mathsf{C}}_2^0}$.^[6]: 148

• Circuit complexity
• Complexity classes

• Articles with short description
• Short description is different from Wikidata