Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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 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 for more details.
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 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 and here).
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 Ryan Williams, which, while very impressive, is still far from solving the problem.
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) 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 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, 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), 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 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 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 Kaveh): The original statement of that theorem can be found in Reducing the Complexity of Reductions 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:
- ...
- 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.
- 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. 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) and Eric Allender (2014), 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.
1M. Sipser. Borel sets and circuit complexity. In Proceedings, 15th ACM Symposium on the Theory of Computing, 1983
