Encyclopedia

AC0

Complexity class of bounded-depth circuits

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated June 7, 2026

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). It thus contains NC⁰, 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.

01Example problems

Integer addition and subtraction are computable in AC⁰, 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⁰ also contains every unary language.

02Descriptive complexity

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.

03Separations

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 ${\mathsf {AC}}^{0}$ . 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 $k>0$ , there exists a family of alternating circuits using depth $\lceil k\ln n/\ln \ln n\rceil$ and size $O\left(2^{(\ln n)^{1/k}}{\frac {n}{(\ln n)^{1/k}}}\right)$ . In particular, setting $k$ to be a large constant, then there exists a family of alternating circuits using depth $O(\ln n/\ln \ln n)\ll O(\ln n)$ , and size only slightly superlinear.

${\mathsf {AC}}^{0}$ can be divided further, into a hierarchy of languages requiring up to 1 layer, 2 layers, etc. Let ${\mathsf {AC}}_{d}^{0}$ be the class of languages decidable by a threshold circuit family of up to depth $d$ : ${\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 ${\mathsf {AC}}_{d}^{0}$ -complete under a uniformity condition: given a grid graph of polynomial length and width $d$ , decide whether two given vertices are connected.

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

Watch videos about AC0Explainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “AC0”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Diagram of an AC0 Circuit.svg by Ylloh, CC0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.