# Which $AC^0$ problems are not “truly feasible”?

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?

• Maybe a problem which requires circuits of depth 10^{10^100}? – Tsuyoshi Ito Sep 1 '10 at 23:36
• @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 2 '10 at 0:18
• 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 2 '10 at 8:52
• 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 3 '10 at 7:04
• @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 3 '10 at 9:10

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.

• 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 4 '10 at 15:01
• @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. – Robin Kothari Oct 4 '10 at 20:53

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

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.

• 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 6:18
• 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
• 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