AC0 📖 Wikipedia

AC⁰ (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).^[1] It thus contains NC⁰, 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, like P/poly, AC⁰ also contains every unary language.

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 predicate, or alternatively by FO(+, ×), or by Turing machine in the logarithmic hierarchy.^[4]

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⁰ circuits, even with non-uniformity. Similarly, computing the majority is also not in ${\displaystyle {\mathsf {AC}}^{0}}$.^[5][1] It follows that AC⁰ is strictly smaller than TC⁰. 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 {AC}}^{0}}$ can be divided further, into a hierarchy of languages requiring up to 1 layer, 2 layers, etc. Let ${\displaystyle {\mathsf {AC}}_{d}^{0}}$ be the class of languages decidable by a threshold circuit family of up to depth ${\displaystyle d}$:$${\displaystyle {\mathsf {AC}}_{1}^{0}\subset {\mathsf {AC}}_{2}^{0}\subset \cdots \subset {\mathsf {AC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {AC}}_{d}^{0}}$$The following problem is ${\displaystyle {\mathsf {AC}}_{d}^{0}}$-complete under a uniformity condition: given a grid graph of polynomial length and width ${\displaystyle d}$, decide whether two given vertices are connected.^[7]

The addition of two ${\displaystyle n}$-bit integers is in ${\displaystyle {\mathsf {AC}}_{3}^{0}}$ but not in ${\displaystyle {\mathsf {AC}}_{2}^{0}}$.^[6]: 148