<p>First of all, would you agree that DNFs and CNFs are a natural object to study? At the very least, if you believe that decision trees are a natural object to study, then so should be DNFs and CNFs, since they are the non-deterministic and co-non-deterministic versions of decision trees.</p>

<p>If you accept that, then I would argue that that $\mathbf{AC}^0$ is a natural generalization of DNFs and CNFs, and therefore it is natural to study it. We can also think about $\mathbf{AC}^0$ as the analogue of the polynomial hierarchy for decision trees. Indeed, there are connections between questions about $\mathbf{AC}^0$ and questions about the polynomial hierarchy relative to oracles (see <a href="https://arxiv.org/abs/1504.03398" rel="nofollow noreferrer">here</a> for a recent example for exploiting such a connection).</p>

<p>That said, the main motivation for studying $\mathbf{AC}^0$ is that it is a good "relaxation" or a "toy problem" for studying larger classes of circuits. A holy grail of complexity theory is to prove that $\mathbf{NP}$ does not have polynomial-size (general) circuits, and we are not anywhere close to proving that. Hence, a natural way to make progress toward this goal is to first try to tackle the following toy problem: prove that $\mathbf{NP}$ does not have polynomial-size $\mathbf{AC}^0$-circuits. This is problem was solved in the celebrated result that showed that such circuits cannot compute the parity function (<a href="https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20-%201984%20-%20Parity%20circuits%20and%20the%20polynomial-time%20hierarchy.pdf" rel="nofollow noreferrer">here</a> and <a href="https://www.sciencedirect.com/science/article/pii/0168007283900386" rel="nofollow noreferrer">here</a>).</p>

<p>This motivation is even more important for a class such as $\mathbf{ACC}^0$. Indeed, this class is less natural by its own right. However, it provides us with another important "toy problem": prove that $\mathbf{NP}$ does not have polynomial-size $\mathbf{ACC}^0$-circuits. This "toy porblem" is still open, and has been open for over 20 years. The strongest result we have is <a href="https://eccc.weizmann.ac.il/report/2017/188/" rel="nofollow noreferrer">this work of Ryan Williams</a>, which, while very impressive, is still far from solving the problem.</p>

CC BY-SA 3.0
2018-03-26T22:27:42.673Z
Note the lower bound for NEXP has been improved to nondeterministic quasipolynomial time, as of December last year https://eccc.weizmann.ac.il/report/2017/188/
Ryan Williams
CC BY-SA 3.0
2018-03-19T09:15:46.633Z
2018-03-28T09:16:07.150Z
2018-03-28T09:16:07.150Z
Or Meir
<blockquote>
  <p>Take AC0. What is a natural thought process that leads to the definition of AC0? Does this class arise intrinsically anywhere?</p>
</blockquote>

<p>The <a href="https://en.wikipedia.org/wiki/LH_(complexity)" rel="nofollow noreferrer">logarithmic time hierarchy (LH)</a> is equal to uniform $\mathbf{AC}^0$. A natural thought process that leads to LH is to look for an analogy of the polynomial time hierarchy (PH) for logarithmic time. You can prove that LH does not collapse<sup>1</sup>, and that its <a href="https://cstheory.stackexchange.com/questions/36839/is-there-a-fine-grained-relation-between-lh-and-ac0">level structure carries over</a> to $\mathbf{AC}^0$. Some problems like addition are in $\mathbf{AC}^0$, but provably not in $\mathbf{NC}^0$. Neither addition nor any other single problem is complete for uniform $\mathbf{AC}^0$, since otherwise LH would collapse. Barrington et al. showed that <a href="http://www.brics.dk/RS/97/25/BRICS-RS-97-25.pdf" rel="nofollow noreferrer">Searching constant width mazes captures the $\mathbf{AC}^0$ hierarchy</a>, so this class arises intrinsically at least sometimes. But that is not the normal case, where $\mathbf{AC}^0$ is used out of convention (instead of a specific depth $k$-subclass). I guess the reason for that convention is that $\mathbf{AC}^0$ is provably a proper subset of $\mathbf{ACC}^0$, so it is weak enough to convey the important point. And $\mathbf{AC}^0$ is closed under composition, which is nice for $\mathbf{AC}^0$ reductions between problems.</p>

<blockquote>
  <p>My problem is that in the case of unbounded fan-in, AND and OR gates behave very differently. Why do we take these gates along with NOT to define a circuit class?</p>
</blockquote>

<p>You probably mean that they behave very different from bounded fan-in gates. I guess $\mathbf{NC}^0$ is too weak and $\mathbf{NC}^1$ is too strong for describing real hardware (circuits). Real hardware needs at least addition and storage-access (<a href="https://en.wikipedia.org/wiki/Multiplexer" rel="nofollow noreferrer">multiplexer</a>), which are both in $\mathbf{AC}^0$. Other nice to have functionality like multiplication and division is in $\mathbf{TC}^0$. It would be interesting whether current hardware contains any functionality (i.e. "fast" processor instruction) not in $\mathbf{TC}^0$. At least I am not aware of any.</p>

<hr>

<p>It should be clear that $\mathbf{AC}^0$, $\mathbf{TC}^0$, and $\mathbf{NC}^1$ are models of parallel computation, especially in their non-uniform version as implemented in actual hardware. I wrote about <a href="https://gentzen.wordpress.com/2017/11/02/alogtime-logcfl-and-threshold-circuits-dreams-of-fast-solutions/" rel="nofollow noreferrer">dreams of fast solutions</a> in the sense of allowing software the same parallel capabilities like hardware already has today. I am still working through all the material referenced there, but at least I have worked through <a href="https://people.cs.umass.edu/~immerman/pub/EricMike60.pdf" rel="nofollow noreferrer">Algebra, Logic and Complexity in Celebration of Eric Allender and Mike Saks</a> by Neil Immerman. The last slides describe a typical place where $\mathbf{AC}^0$ occurs, namely all "natural" NP complete problem stay complete under $\mathbf{AC}^0$ reductions, and all such problems are actually $\mathbf{AC}^0$ isomorphic. Also true for $\mathbf{NC}^1$, $\mathbf{sAC}^1$, L, NL, P, PSPACE, etc (complete problems). <strong>Edit (in response to Kaveh)</strong>: The original statement of that theorem can be found in <a href="http://ftp.cs.rutgers.edu/pub/allender/stoc97.pdf" rel="nofollow noreferrer">Reducing the Complexity of Reductions</a> by M. Agrawala, E. Allender, R. Impagliazzo, T. Pitassi, S. Rudich from 2001:</p>

<blockquote>
  <p>More precisely, we show that for any class $\mathcal{C}$ closed under uniform $\mathbf{TC}^0$-computable many-one reductions, the following three theorems hold:</p>
  
  <ol>
  <li>...</li>
  <li>The sets complete for $\mathcal{C}$ under P-uniform $\mathbf{AC}^0$ reductions are all isomorphic under isomorphisms computable and invertible by P-uniform $\mathbf{AC}^0$ circuits of depth-three.</li>
  <li>There are sets complete for $\mathcal{C}$ under Dlogtime-uniform $\mathbf{AC}^0$ reductions that are not isomorphic under any isomorphism computed by (even non-uniform) $\mathbf{AC}^0$ circuits of depth two.</li>
  </ol>
</blockquote>

<p>The fact that P-uniform $\mathbf{AC}^0$ circuits are needed is slightly unexpected, since uniform $\mathbf{AC}^0$ normally means Dlogtime-uniform $\mathbf{AC}^0$ (i.e. FOL and LH are only known to be equal to Dlogtime-uniform $\mathbf{AC}^0$, not to P-uniform $\mathbf{AC}^0$). Manindra Agrawal, <a href="https://www.cse.iitk.ac.in/users/manindra/isomorphism/uniform-ac0-iso.pdf" rel="nofollow noreferrer">The First-Order Isomorphism Theorem.</a> FSTTCS 2001, LNCS 2245: 70-82, is mentioned last in Immerman's survey, since it seems to prove that P-uniform can be replaced by Dlogtime-uniform. But it doesn't preserve the depth-three part of the theorem. There are surveys by <a href="https://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf" rel="nofollow noreferrer">Manindra Agrawal (2009)</a> and <a href="http://ftp.cs.rutgers.edu/pub/allender/isomorphism.pdf" rel="nofollow noreferrer">Eric Allender (2014)</a>, but I only found them after writing this answer (while trying to understand whether Kaveh's point about the supreme importance of FOL is correct), and I have not read them yet.</p>

<p>1<sub>M. Sipser. Borel sets and circuit complexity. In Proceedings, 15th ACM Symposium on the Theory of Computing, 1983</sub></p>

CC BY-SA 3.0
2018-03-25T17:54:10.137Z
I am not sure that it makes sense to compare real hardware with abstract class like TC0, real hardware has fixed word length and operations take place over then. Also note that real hardwares these days implement functions like SHA1 and SHA256 as operations.
Kaveh
CC BY-SA 3.0
2018-03-25T17:57:06.997Z
Re completeness, Allender et. al. iirc prove that any function which is complete for NP under AC0 functions is complete for it under polynomial p-projections. Use of AC0 for reductions is mainly for convince as it is easy to define them using FOL as Jan mentions in his answer and are sufficiently weak for most purposes.
Kaveh
CC BY-SA 3.0
2018-03-26T08:49:19.277Z
@Kaveh Re completeness, you seem to believe that I misunderstood what has been proved. Maybe linking to an overview presentation was a bad idea (Chinese whispers/telephone), but it is the one I actually worked through. I now added a link to the original publication and explicitly quoted the correct theorem. It reveals disturbing details about non-uniform, P-uniform and Dlogtime-uniform, which are missing from the overview presentation. Interestingly, those details refute your conjecture that AC0 occurs mainly for convenience (or would be just a substitute for FOL).
Thomas Klimpel
CC BY-SA 3.0
2018-03-26T09:52:10.763Z
@Kaveh There are pros and cons of comparing abstract circuit classes to real hardware. The current word length of 64-bit is big enough for the comparison to make sense. On the pro side, we have that the sort of parallelism expressed by those classes is exploited in real hardware, but is currently too low level for being exploited explicitly by user level software. (However, the instruction scheduling of modern processors does exploit such low level parallelism.) On the con side, things like area and wiring are ignored. And for NC1 the treacherous fact that the circuit size is often quadratic.
Thomas Klimpel
CC BY-SA 3.0
2018-03-25T16:28:33.500Z
2018-03-30T16:10:59.637Z
2018-03-30T16:10:59.637Z
Thomas Klimpel
<p>I'll add as an answer here that AC0 is a good (arguably, the best) way to think about several results in complexity theory, like BPP in PH, Toda's theorem, etc.  (This perspective is e.g. emphasized in <a href="https://www.ccs.neu.edu/home/viola/papers/moti.pdf" rel="nofollow noreferrer">my book</a>.)  So I'd say that if you care about PH you also care about AC0.</p>
<p>I also find it very natural in that it allows for composition of tasks (by stacking circuits) and can do useful things like adding integers.</p>

CC BY-SA 4.0
2024-11-21T19:16:14.900Z
2024-11-21T19:16:14.900Z
Manu
<p>The class $\mathbf{AC}^0$ arises very naturally as the circuit characterization of problems definable by formulas of first-order logic. A language over the alphabet $\{ 0,1 \}$ is in $\mathbf{AC}^0$ if and only if it is definable in first-order logic in the language of word structures. 
See e.g. <a href="https://doi.org/10.1007/978-1-4612-0539-5" rel="noreferrer">Immerman's book</a> for more details. </p>

<p>$\mathbf{AC}^0$ also arises naturally when studying theories of bounded arithmetic. The simplest of these theories $\mathbf{V}_0$ corresponds precisely to $\mathbf{AC}^0$ in that the functions and relations definable in the theory are exactly those in uniform $\mathbf{AC}^0$. See the <a href="http://www.cambridge.org/us/academic/subjects/mathematics/logic-categories-and-sets/logical-foundations-proof-complexity#3MTDRzxJSwuOvA2P.97" rel="noreferrer">book of Cook and Nguyen</a> for more details. </p>

CC BY-SA 3.0
2018-03-26T17:43:22.050Z
Thanks. I'm also looking for a similar answer for ACC0 instead.
theorik
CC BY-SA 3.0
2018-03-27T10:06:01.607Z
I think you should probably edit this question to be just about AC^0 and ask a separate question for ACC^0.
Jan Johannsen
CC BY-SA 3.0
2018-03-20T09:23:01.323Z
2018-03-20T09:23:01.323Z
Jan Johannsen
<p>Take AC0. 
What is a natural thought process that leads to the definition of AC0? 
Does this class arise intrinsically anywhere? </p>

<p>My problem is that in the case of unbounded fan-in, AND and OR gates behave very differently. Why do we take these gates along with NOT to define a circuit class? </p>

<cc.complexity-theory><complexity-classes><circuit-complexity>
Why is the circuit class AC0 unavoidable?
theorik
# Why is the circuit class AC0 unavoidable?

(Asked by: username_0 on 2018-03-19)

Take AC0.
What is a natural thought process that leads to the definition of AC0?
Does this class arise intrinsically anywhere?

My problem is that in the case of unbounded fan-in, AND and OR gates behave very differently. Why do we take these gates along with NOT to define a circuit class?

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity


---

## 4 answers

### Answer by username_6 on 2018-03-20. Score: 12 | Accepted answer

The class $\mathbf{AC}^0$ arises very naturally as the circuit characterization of problems definable by formulas of first-order logic. A language over the alphabet $\{ 0,1 \}$ is in $\mathbf{AC}^0$ if and only if it is definable in first-order logic in the language of word structures.
See e.g. [Immerman's book](https://doi.org/10.1007/978-1-4612-0539-5) for more details.

$\mathbf{AC}^0$ also arises naturally when studying theories of bounded arithmetic. The simplest of these theories $\mathbf{V}\_0$ corresponds precisely to $\mathbf{AC}^0$ in that the functions and relations definable in the theory are exactly those in uniform $\mathbf{AC}^0$. See the [book of Cook and Nguyen](http://www.cambridge.org/us/academic/subjects/mathematics/logic-categories-and-sets/logical-foundations-proof-complexity#3MTDRzxJSwuOvA2P.97) for more details.

> **Comments:**
> **username_0**: Thanks. I'm also looking for a similar answer for ACC0 instead.  
> **username_6**: I think you should probably edit this question to be just about AC^0 and ask a separate question for ACC^0.  

---

### Answer by username_1 on 2018-03-19. Score: 9

First of all, would you agree that DNFs and CNFs are a natural object to study? At the very least, if you believe that decision trees are a natural object to study, then so should be DNFs and CNFs, since they are the non-deterministic and co-non-deterministic versions of decision trees.

If you accept that, then I would argue that that $\mathbf{AC}^0$ is a natural generalization of DNFs and CNFs, and therefore it is natural to study it. We can also think about $\mathbf{AC}^0$ as the analogue of the polynomial hierarchy for decision trees. Indeed, there are connections between questions about $\mathbf{AC}^0$ and questions about the polynomial hierarchy relative to oracles (see [here](https://arxiv.org/abs/1504.03398) for a recent example for exploiting such a connection).

That said, the main motivation for studying $\mathbf{AC}^0$ is that it is a good "relaxation" or a "toy problem" for studying larger classes of circuits. A holy grail of complexity theory is to prove that $\mathbf{NP}$ does not have polynomial-size (general) circuits, and we are not anywhere close to proving that. Hence, a natural way to make progress toward this goal is to first try to tackle the following toy problem: prove that $\mathbf{NP}$ does not have polynomial-size $\mathbf{AC}^0$-circuits. This is problem was solved in the celebrated result that showed that such circuits cannot compute the parity function ([here](https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20-%201984%20-%20Parity%20circuits%20and%20the%20polynomial-time%20hierarchy.pdf) and [here](https://www.sciencedirect.com/science/article/pii/0168007283900386)).

This motivation is even more important for a class such as $\mathbf{ACC}^0$. Indeed, this class is less natural by its own right. However, it provides us with another important "toy problem": prove that $\mathbf{NP}$ does not have polynomial-size $\mathbf{ACC}^0$-circuits. This "toy porblem" is still open, and has been open for over 20 years. The strongest result we have is [this work of username_2](https://eccc.weizmann.ac.il/report/2017/188/), which, while very impressive, is still far from solving the problem.

> **Comments:**
> **username_2**: Note the lower bound for NEXP has been improved to nondeterministic quasipolynomial time, as of December last year https://eccc.weizmann.ac.il/report/2017/188/  

---

### Answer by username_3 on 2018-03-25. Score: 5

> Take AC0. What is a natural thought process that leads to the definition of AC0? Does this class arise intrinsically anywhere?

The [logarithmic time hierarchy (LH)](https://en.wikipedia.org/wiki/LH_(complexity)) is equal to uniform $\mathbf{AC}^0$. A natural thought process that leads to LH is to look for an analogy of the polynomial time hierarchy (PH) for logarithmic time. You can prove that LH does not collapse1, and that its [level structure carries over](https://cstheory.stackexchange.com/questions/36839/is-there-a-fine-grained-relation-between-lh-and-ac0) to $\mathbf{AC}^0$. Some problems like addition are in $\mathbf{AC}^0$, but provably not in $\mathbf{NC}^0$. Neither addition nor any other single problem is complete for uniform $\mathbf{AC}^0$, since otherwise LH would collapse. Barrington et al. showed that [Searching constant width mazes captures the $\mathbf{AC}^0$ hierarchy](http://www.brics.dk/RS/97/25/BRICS-RS-97-25.pdf), so this class arises intrinsically at least sometimes. But that is not the normal case, where $\mathbf{AC}^0$ is used out of convention (instead of a specific depth $k$-subclass). I guess the reason for that convention is that $\mathbf{AC}^0$ is provably a proper subset of $\mathbf{ACC}^0$, so it is weak enough to convey the important point. And $\mathbf{AC}^0$ is closed under composition, which is nice for $\mathbf{AC}^0$ reductions between problems.

> My problem is that in the case of unbounded fan-in, AND and OR gates behave very differently. Why do we take these gates along with NOT to define a circuit class?

You probably mean that they behave very different from bounded fan-in gates. I guess $\mathbf{NC}^0$ is too weak and $\mathbf{NC}^1$ is too strong for describing real hardware (circuits). Real hardware needs at least addition and storage-access ([multiplexer](https://en.wikipedia.org/wiki/Multiplexer)), which are both in $\mathbf{AC}^0$. Other nice to have functionality like multiplication and division is in $\mathbf{TC}^0$. It would be interesting whether current hardware contains any functionality (i.e. "fast" processor instruction) not in $\mathbf{TC}^0$. At least I am not aware of any.

---

It should be clear that $\mathbf{AC}^0$, $\mathbf{TC}^0$, and $\mathbf{NC}^1$ are models of parallel computation, especially in their non-uniform version as implemented in actual hardware. I wrote about [dreams of fast solutions](https://gentzen.wordpress.com/2017/11/02/alogtime-logcfl-and-threshold-circuits-dreams-of-fast-solutions/) in the sense of allowing software the same parallel capabilities like hardware already has today. I am still working through all the material referenced there, but at least I have worked through [Algebra, Logic and Complexity in Celebration of Eric Allender and Mike Saks](https://people.cs.umass.edu/~immerman/pub/EricMike60.pdf) by Neil Immerman. The last slides describe a typical place where $\mathbf{AC}^0$ occurs, namely all "natural" NP complete problem stay complete under $\mathbf{AC}^0$ reductions, and all such problems are actually $\mathbf{AC}^0$ isomorphic. Also true for $\mathbf{NC}^1$, $\mathbf{sAC}^1$, L, NL, P, PSPACE, etc (complete problems). **Edit (in response to username_4)**: The original statement of that theorem can be found in [Reducing the Complexity of Reductions](http://ftp.cs.rutgers.edu/pub/allender/stoc97.pdf) by M. Agrawala, E. Allender, R. Impagliazzo, T. Pitassi, S. Rudich from 2001:

> More precisely, we show that for any class $\mathcal{C}$ closed under uniform $\mathbf{TC}^0$-computable many-one reductions, the following three theorems hold:
>
> 1. ...
> 2. The sets complete for $\mathcal{C}$ under P-uniform $\mathbf{AC}^0$ reductions are all isomorphic under isomorphisms computable and invertible by P-uniform $\mathbf{AC}^0$ circuits of depth-three.
> 3. There are sets complete for $\mathcal{C}$ under Dlogtime-uniform $\mathbf{AC}^0$ reductions that are not isomorphic under any isomorphism computed by (even non-uniform) $\mathbf{AC}^0$ circuits of depth two.

The fact that P-uniform $\mathbf{AC}^0$ circuits are needed is slightly unexpected, since uniform $\mathbf{AC}^0$ normally means Dlogtime-uniform $\mathbf{AC}^0$ (i.e. FOL and LH are only known to be equal to Dlogtime-uniform $\mathbf{AC}^0$, not to P-uniform $\mathbf{AC}^0$). Manindra Agrawal, [The First-Order Isomorphism Theorem.](https://www.cse.iitk.ac.in/users/manindra/isomorphism/uniform-ac0-iso.pdf) FSTTCS 2001, LNCS 2245: 70-82, is mentioned last in Immerman's survey, since it seems to prove that P-uniform can be replaced by Dlogtime-uniform. But it doesn't preserve the depth-three part of the theorem. There are surveys by [Manindra Agrawal (2009)](https://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf) and [Eric Allender (2014)](http://ftp.cs.rutgers.edu/pub/allender/isomorphism.pdf), but I only found them after writing this answer (while trying to understand whether username_4's point about the supreme importance of FOL is correct), and I have not read them yet.

1M. Sipser. Borel sets and circuit complexity. In Proceedings, 15th ACM Symposium on the Theory of Computing, 1983

> **Comments:**
> **username_4**: I am not sure that it makes sense to compare real hardware with abstract class like TC0, real hardware has fixed word length and operations take place over then. Also note that real hardwares these days implement functions like SHA1 and SHA256 as operations.  
> **username_4**: Re completeness, Allender et. al. iirc prove that any function which is complete for NP under AC0 functions is complete for it under polynomial p-projections. Use of AC0 for reductions is mainly for convince as it is easy to define them using FOL as Jan mentions in his answer and are sufficiently weak for most purposes.  
> **username_3**: @username_4 Re completeness, you seem to believe that I misunderstood what has been proved. Maybe linking to an overview presentation was a bad idea (Chinese whispers/telephone), but it is the one I actually worked through. I now added a link to the original publication and explicitly quoted the correct theorem. It reveals disturbing details about non-uniform, P-uniform and Dlogtime-uniform, which are missing from the overview presentation. Interestingly, those details refute your conjecture that AC0 occurs mainly for convenience (or would be just a substitute for FOL).  
> **username_3**: @username_4 There are pros and cons of comparing abstract circuit classes to real hardware. The current word length of 64-bit is big enough for the comparison to make sense. On the pro side, we have that the sort of parallelism expressed by those classes is exploited in real hardware, but is currently too low level for being exploited explicitly by user level software. (However, the instruction scheduling of modern processors does exploit such low level parallelism.) On the con side, things like area and wiring are ignored. And for NC1 the treacherous fact that the circuit size is often quadratic.  

---

### Answer by username_5 on 2024-11-21. Score: 2

I'll add as an answer here that AC0 is a good (arguably, the best) way to think about several results in complexity theory, like BPP in PH, Toda's theorem, etc. (This perspective is e.g. emphasized in [my book](https://www.ccs.neu.edu/home/viola/papers/moti.pdf).) So I'd say that if you care about PH you also care about AC0.

I also find it very natural in that it allows for composition of tasks (by stacking circuits) and can do useful things like adding integers.


---

