AC0

---

title: "AC0" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["circuit-complexity", "complexity-classes"] description: "Complexity class of bounded-depth circuits" topic_path: "general/circuit-complexity" source: "https://en.wikipedia.org/wiki/AC0" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Complexity class of bounded-depth circuits ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/b/be/Diagram_of_an_AC0_Circuit.svg" caption="Diagram of an AC⁰ circuit: The n input bits are on the bottom and the top gate produces the output; the circuit consists of AND- and OR-gates of polynomial fan-in each, and the alternation depth is bounded by a constant."] ::

AC0 (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 NC0, 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.

Example problems

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

Descriptive complexity

From a descriptive complexity viewpoint, DLOGTIME-uniform AC0 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.{{cite book | last = Immerman | first = N. | author-link = Neil Immerman | page = 85 | publisher = Springer | title = Descriptive Complexity | title-link= Descriptive Complexity | year = 1999}}

Separations

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 AC0 circuits, even with non-uniformity. Similarly, computing the majority is also not in \mathsf{AC}^0. It follows that AC0 is strictly smaller than TC0. Note that "PARITY" is also called "XOR" in the literature.

However, PARITY is only barely out of AC0, 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}^0_d be the class of languages decidable by a threshold circuit family of up to depth d:\mathsf{AC}^0_1 \subset \mathsf{AC}^0_2 \subset \cdots \subset \mathsf{AC}^0 = \bigcup_{d=1}^\infty \mathsf{AC}^0_dThe following problem is \mathsf{AC}^0_d-complete under a uniformity condition. Given a grid graph of polynomial length and width k, decide whether a given pair of vertices are connected.

The addition of two n-bit integers is in \mathsf{AC}^0_3 but not in \mathsf{AC}^0_2.

References

References

1. (July 18, 2000). "Lecture 2: The Complexity of Some Problems". IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity.
2. (2015). "Lecture 5: Feb 4, 2015".
3. (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory.
4. (2009). "Computational complexity. A modern approach". [[Cambridge University Press]].
5. (1994-07-27). "Circuit Complexity and Neural Networks". The MIT Press.
6. (1998). "Stacs 98". Springer.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::