17

Neil Immerman's famous Picture of The World is the following (click to enlarge):

                                       

His "Truly feasible" class includes no other class; my question is then:

What is an AC0 problem which is considered to be unpractical, and why?

Glorfindel
  • 359
  • 1
  • 4
  • 10
Michaël Cadilhac
  • 3,946
  • 22
  • 39
  • 2
    Maybe a problem which requires circuits of depth 10^{10^100}? – Tsuyoshi Ito Sep 01 '10 at 23:36
  • @Tsuyoshi, I think Michael is asking for an example of a real world problem in AC0 that (for example) requires circuits of depth 10^{10^100}. – Ross Snider Sep 01 '10 at 23:57
  • 1
    @Ross: I do not think so because he did not mention “real world” and he asked “why”; I think that my previous comment answers at least the “why” part. However, admittedly I do not have an example of “natural” problems which are in AC0 and require circuits of depth 10^{10^100}. – Tsuyoshi Ito Sep 02 '10 at 00:18
  • 2
    There are numerous interesting real-world problems that could be solved in constant time and constant space (in virtually any model of computation), yet people have now idea how to solve them in practice. Extreme examples are computing certain constants; we could hard-code the right answer (e.g., 0 or 1), but we don't know the answer yet. – Jukka Suomela Sep 02 '10 at 08:52
  • 1
    Jukka: those are problem instances. Diophantine equations (like Fermat's) are undecidable as a class, even if individual instances which we have decided actually have constant depth circuits. – András Salamon Sep 03 '10 at 07:04
  • 1
    @András: If you prefer decision problems with infinitely many "yes" and "no" instances: Let $L$ consist of all even numbers and $x$, where $x = 1$ if the white player has a winning strategy in chess and otherwise $x = 3$. Trivially, there exists a very simple family of circuits that decides $L$, but I'd still claim that it's "unpractical". Not because the circuit would be huge, but because designing the circuit would be a huge computational effort... Cheating?-) – Jukka Suomela Sep 03 '10 at 09:10
  • The difficulty then isn't in the circuit. The language is either "even+1" or "even+3", we just don't know which until this extraneous problem is solved. – András Salamon Sep 03 '10 at 12:59

3 Answers3

16

If you want an example of an AC0 function that requires depth $d$, and cannot be computed by AC0 circuits of depth $d-1$, then try the Sipser functions $S^{d,n}$. The superscript $d$ is depth needed for a polynomial-size AC0 circuit. With depth $d-1$, the circuit would need exponentially many gates.

So computing $S^{d,n}$ for $d = 10^{10^{100}}$ would not be "truly feasible."

EDIT: Your question also asks why this would not be feasible. I guess the reason is that $10^{10^{100}}$ is more than the number of atoms in the visible universe.

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
  • That's great, thank you! Maybe you can add an informal definition of the Sipser functions? I didn't know about that name. – Michaël Cadilhac Oct 04 '10 at 15:01
  • 1
    @Michaël: Unfortunately I don't have a good intuitive definition for the Sipser functions. The idea is to make a function of d quantifiers such that no depth d-1 circuit can compute it. So we want the d quantifiers to quantify over a very large number of variables. There's a nice article by Iddo Tzameret, entitled "Håstad's Separation of Constant-Depth Circuits Using Sipser Functions" (http://itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf) that defines the functions formally on page 7. – Robin Kothari Oct 04 '10 at 20:53
9

All this hierarchy is intentionally robust under polynomial changes of the input size. Any class in it can thus contains functions whose complexity is say n^{1000000000} which would be theoretically "feasible" but certainly not practically so. These, however will most likely be very artificial problems. In particular by a counting argument there exists a family of DNF formula (=AC^0 depth 2 circuits) of size n^1000000 which no algorithm whose running time is less than n^999999 can compute. (In a uniform setting we expect something similar but can't prove it.)

Noam
  • 9,369
  • 47
  • 58
1

The halting problem when the input is represented in unary is in AC^0 and yet quite unfeasible in reality. I'm not sure this is what you meant, but it could be what Immerman meant.

Elad
  • 139
  • 3
  • I guess the classes in the diagram are defined with some notion of uniformity? Otherwise the upward direction would not represent containment, since P does not contain non-uniform AC^0. – Robin Kothari Sep 13 '10 at 06:18
  • 1
    Yes, the classes in the picture are uniform. E.g., it is required that an $ AC^0 $ circuit family can be encoded as a language accepted by a weak uniform complexity class like FO (where FO is the class of ${0,1}$ strings defined by first-order formulas in the language $ {0,max; X,BIT,\le,=} $, for $X$ the only unspecified unary predicate). – Iddo Tzameret Sep 13 '10 at 11:35
  • 3
    Point well taken. As an alternative, following Erdos, one could instead suggest the problem that for any input, outputs the Ramsey number for red six and blue six. – Elad Sep 17 '10 at 18:30