3
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I'm also looking for a similar answer for ACC0 instead. $\endgroup$ – theorik Mar 26 '18 at 17:43
  • 2
    $\begingroup$ I think you should probably edit this question to be just about AC^0 and ask a separate question for ACC^0. $\endgroup$ – Jan Johannsen Mar 27 '18 at 10:06
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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:

  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. 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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Mar 25 '18 at 17:54
  • $\begingroup$ 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. $\endgroup$ – Kaveh Mar 25 '18 at 17:57
  • $\begingroup$ @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). $\endgroup$ – Thomas Klimpel Mar 26 '18 at 8:49
  • $\begingroup$ @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. $\endgroup$ – Thomas Klimpel Mar 26 '18 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.