22
$\begingroup$

We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known not to be in AC0 are also not computable by a constant-depth formula. However, since it's an easier model, I'm guessing there are more problems known to be not computable in this model. Has this been studied? (I'm guessing it has been, but I'm probably not using the right search terms.)

Specifically I am interested in the following question: Is there some function f, which can be computed by an AC0 circuit of size S, but needs a constant-depth formula of size at least quadratic in S, or super-polynomial in S? What's the best known result of this kind?

In case it is not clear what I mean by constant-depth formula, I mean a formula which if you write out as a tree (with internal nodes being AND/OR/NOT gates, and leaves being inputs), then this tree has constant height. Equivalently, a constant-depth formula is a constant-depth circuit in which all non-input gates have fanout 1.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

It is easy to convert a constant depth circuit to a constant depth formula of the same depth with polynomial size increase, by making copies of gates used more than once. If the depth of the circuit is $d$ and its size is $O(p(n))$, the formula will have depth $d$ and size $O((p(n))^d)$. Therefore the answer is no.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ this gives more than a quadratic increase in size. (Though, not super-polynomial increase, of course.) $\endgroup$
    – Iddo Tzameret
    Commented Aug 17, 2010 at 11:18
  • 2
    $\begingroup$ Thanks for the answer. Any idea about a particular function f which has a constant-depth circuit of size S, but needs a formula of size S^2, or S^10, etc.? $\endgroup$
    – Robin Kothari
    Commented Aug 17, 2010 at 15:48
  • 3
    $\begingroup$ I think the relation between depth and circuit size is still open (It is known that "depth" is teta of formula size). See chapters 7 and 8 in Wegener's book "Complexity of boolean functions" for some function with explicit formula size lower-bounds. There is one with almost quadratic increase ($n^2/log n$), didn't notice anything better. $\endgroup$
    – Kaveh
    Commented Aug 17, 2010 at 21:41
17
$\begingroup$

This question has been completely resolved (up to constant factors) by a recent result of Benjamin Rossman (http://eccc.hpi-web.de/report/2013/169/).

As Kaveh points out above, a depth $d$, size $S$, circuit can be converted to a depth $d$, size $S^d$ formula.

Rossman shows that this is essentially tight. For any depth $d$, he exhibits a function that can be computed by a constant-depth circuit of depth $d$ and size $S = O(n^3)$, but any constant-depth formula (or even a $\sqrt{\log n}$-depth formula) needs size $S^{\Omega(d)}$ to compute it.

(Forgot to say this before: Thanks to Benjamin Rossman for letting me know about this result.)

Improve this answer
$\endgroup$

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.