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

CC BY-SA 2.5
2010-09-04T04:36:21.870Z
2010-09-04T04:45:01.463Z
2010-09-04T04:45:01.463Z
Noam
<p>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.</p>

CC BY-SA 2.5
2010-09-13T06:18:45.423Z
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
CC BY-SA 2.5
2010-09-13T11:35:25.367Z
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
CC BY-SA 2.5
2010-09-17T18:30:59.213Z
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
CC BY-SA 2.5
2010-09-13T03:00:45.610Z
2010-09-13T03:00:45.610Z
Elad
<p>If you want an example of an AC<sup>0</sup> function that requires depth $d$, and cannot be computed by AC<sup>0</sup> circuits of depth $d-1$, then try the Sipser functions $S^{d,n}$. The superscript $d$ is depth needed for a polynomial-size AC<sup>0</sup> circuit. With depth $d-1$, the circuit would need exponentially many gates.</p>

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

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

CC BY-SA 2.5
2010-10-04T15:01:31.140Z
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
CC BY-SA 2.5
2010-10-04T20:53:18.163Z
@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
CC BY-SA 2.5
2010-09-02T00:13:41.500Z
2010-09-02T00:13:41.500Z
Robin Kothari
<p>Neil Immerman's famous Picture of The World is the following (click to enlarge):</p>

<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="https://i.sstatic.net/1lGeX.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1lGeX.jpg" height="500"></a></p>

<p>His "Truly feasible" class includes no other class; my question is then:</p>

<blockquote>
  <p>What is an AC<sup>0</sup> problem which is considered to be unpractical, and why?</p>
</blockquote>

CC BY-SA 2.5
2010-09-01T23:36:23.520Z
Maybe a problem which requires circuits of depth 10^{10^100}?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-01T23:57:18.543Z
@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
CC BY-SA 2.5
2010-09-02T00:18:47.120Z
@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
CC BY-SA 2.5
2010-09-02T08:52:23.140Z
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
CC BY-SA 2.5
2010-09-03T07:04:04.350Z
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
CC BY-SA 2.5
2010-09-03T09:10:31.170Z
@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
CC BY-SA 2.5
2010-09-03T12:59:31.847Z
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
<cc.complexity-theory><circuit-complexity>
Which $AC^0$ problems are not "truly feasible"?
Michaël Cadilhac
# Which $AC^0$ problems are not "truly feasible"?

(Asked by: username_0 on 2010-09-01)

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

[![](https://i.sstatic.net/1lGeX.jpg)](https://i.sstatic.net/1lGeX.jpg)

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?

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: Maybe a problem which requires circuits of depth 10^{10^100}?  
> **username_2**: @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}.  
> **username_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}.  
> **username_3**: 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.  
> **username_4**: 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.  
> **username_3**: @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?-)  
> **username_4**: 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.  

---

## 3 answers

### Answer by username_7 on 2010-09-02. Score: 16 | Accepted answer

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.

> **Comments:**
> **username_0**: That's great, thank you!  Maybe you can add an informal definition of the Sipser functions?  I didn't know about that name.  
> **username_7**: @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 username_8, 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.  

---

### Answer by username_5 on 2010-09-04. Score: 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.)


---

### Answer by username_6 on 2010-09-13. Score: 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.

> **Comments:**
> **username_7**: 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.  
> **username_8**: 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).  
> **username_6**: 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.  

---

