17
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Maybe a problem which requires circuits of depth 10^{10^100}? $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 1, 2010 at 23:36
  • 1
    $\begingroup$ @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}. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 2, 2010 at 0:18
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    Commented Sep 2, 2010 at 8:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Sep 3, 2010 at 7:04
  • 1
    $\begingroup$ @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?-) $\endgroup$
    – Jukka Suomela
    Commented Sep 3, 2010 at 9:10

3 Answers 3

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's great, thank you! Maybe you can add an informal definition of the Sipser functions? I didn't know about that name. $\endgroup$
    – Michaël Cadilhac
    Commented Oct 4, 2010 at 15:01
  • 1
    $\begingroup$ @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" (itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf) that defines the functions formally on page 7. $\endgroup$
    – Robin Kothari
    Commented Oct 4, 2010 at 20:53
9
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Commented Sep 13, 2010 at 6:18
  • 1
    $\begingroup$ 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). $\endgroup$
    – Iddo Tzameret
    Commented Sep 13, 2010 at 11:35
  • 3
    $\begingroup$ 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. $\endgroup$
    – Elad
    Commented Sep 17, 2010 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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