AC0

File:Diagram of an AC0 Circuit.svg

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⁰,{{cite web|title=Lecture 2: The Complexity of Some Problems|url=http://people.clarkson.edu/~alexis/PCMI/Notes/lectureB02.pdf|first1=David Mix|last1=Barrington|first2=Alexis|last2=Maciel|work=IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity|date=July 18, 2000}} but multiplication is not (specifically, when the inputs are two integers under the usual binary{{Cite web|last1=Kayal|first1=Neeraj|author-link1=Neeraj Kayal|last2=Hegde|first2=Sumant|date=2015|title=Lecture 5: Feb 4, 2015|url=https://www.csa.iisc.ac.in/~chandan/courses/arithmetic_circuits/notes/lec5.pdf|url-status=live|access-date=2021-10-16|website=E0 309: Topics in Complexity Theory|archive-url=https://web.archive.org/web/20211016230049/https://www.csa.iisc.ac.in/~chandan/courses/arithmetic_circuits/notes/lec5.pdf |archive-date=2021-10-16 }} 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.{{cite book

| last = Immerman | first = N. | author-link = Neil Immerman

| page = [https://archive.org/details/descriptivecompl00imme_115/page/n96 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 AC⁰ circuits, even with non-uniformity. Similarly, computing the majority is also not in $\mathsf{AC}^0$ .{{cite journal | zbl=0534.94008 | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984}}{{cite book | zbl=1193.68112 | last1=Arora | first1=Sanjeev | author1-link=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | url=https://archive.org/details/computationalcom00aror | url-access=limited | publisher=Cambridge University Press | year=2009 | isbn=978-0-521-42426-4 | pages=[https://archive.org/details/computationalcom00aror/page/n142 117]–118, 287}}

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)$ .{{Cite book |last1=Parberry |first1=Ian |url=https://direct.mit.edu/books/book/2708/Circuit-Complexity-and-Neural-Networks |title=Circuit Complexity and Neural Networks |last2=Garey |first2=Michael R. |last3=Meyer |first3=Albert |date=1994-07-27 |publisher=The MIT Press |isbn=978-0-262-28124-9 |language=en |doi=10.7551/mitpress/1836.001.0001}}{{Pg|page=135}} 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.

More precise bounds follow from switching lemma. Using them, it has been shown that there is an oracle separation between the polynomial hierarchy and PSPACE.

$\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_d$ The 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.{{Cite book |last1=Barrington |first1=David A. Mix |last2=Lu |first2=Chi-Jen |last3=Miltersen |first3=Peter Bro |last4=Skyum |first4=Sven |date=1998 |editor-last=Morvan |editor-first=Michel |editor2-last=Meinel |editor2-first=Christoph |editor3-last=Krob |editor3-first=Daniel |chapter=Searching constant width mazes captures the AC0 hierarchy |chapter-url=https://link.springer.com/chapter/10.1007/BFb0028550 |title=Stacs 98 |series=Lecture Notes in Computer Science |volume=1373 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=73–83 |doi=10.1007/BFb0028550 |isbn=978-3-540-69705-3}}

The addition of two $n$ -bit integers is in $\mathsf{AC}^0_3$ but not in $\mathsf{AC}^0_2$ .{{Pg|page=148}}

References

Category:Circuit complexity

Category:Complexity classes