AC0 explained

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.

Example problems

Integer addition and subtraction are computable in AC⁰,^[1] but multiplication is not (specifically, when the inputs are two integers under the usual binary^[2] or base-10 representations of integers).

Since it is a circuit class, like P/poly, AC⁰ also contains every unary language.

Descriptive 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.^[3]

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 AC⁰ circuits, even with non-uniformity. Similarly, computing the majority is also not in

.^{[4] [5]} 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

, there exists a family of alternating circuits using depth and size .^[6] 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 :$$\backslash mathsf^0\_1\; \backslash subset\; \backslash mathsf^0\_2\; \backslash subset\; \backslash cdots\; \backslash subset\; \backslash mathsf^0\; =\; \backslash bigcup\_^\backslash infty\; \backslash mathsf^0\_d$$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.^[7]

The addition of two

-bit integers is in but not in .

Notes and References

1. Web site: Lecture 2: The Complexity of Some Problems. David Mix. Barrington. Alexis. Maciel. IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity. July 18, 2000.
2. Web site: Kayal. Neeraj. Neeraj Kayal. Hegde. Sumant. 2015. Lecture 5: Feb 4, 2015. live. 2021-10-16. E0 309: Topics in Complexity Theory. https://web.archive.org/web/20211016230049/https://www.csa.iisc.ac.in/~chandan/courses/arithmetic_circuits/notes/lec5.pdf . 2021-10-16 .
3. Book: Immerman, N. . Neil Immerman . 85 . Springer . Descriptive Complexity . Descriptive Complexity . 1999.
4. 0534.94008 . Furst . Merrick . Saxe . James B. . James B. Saxe . Sipser . Michael . Michael Sipser . 10.1007/BF01744431 . 1 . Mathematical Systems Theory . 738749 . 13–27 . Parity, circuits, and the polynomial-time hierarchy . 17 . 1984.
5. Book: 1193.68112 . Arora . Sanjeev . Sanjeev Arora (computer scientist) . Barak . Boaz . Computational complexity. A modern approach . limited . . 2009 . 978-0-521-42426-4 . 117–118, 287.
6. Book: Parberry . Ian . Circuit Complexity and Neural Networks . Garey . Michael R. . Meyer . Albert . 1994-07-27 . The MIT Press . 978-0-262-28124-9 . en . 10.7551/mitpress/1836.001.0001.
7. Book: Barrington . David A. Mix . Lu . Chi-Jen . Miltersen . Peter Bro . Skyum . Sven . 1998 . Morvan . Michel . Meinel . Christoph . Krob . Daniel . Searching constant width mazes captures the AC0 hierarchy . https://link.springer.com/chapter/10.1007/BFb0028550 . Stacs 98 . Lecture Notes in Computer Science . 1373 . en . Berlin, Heidelberg . Springer . 73–83 . 10.1007/BFb0028550 . 978-3-540-69705-3.