What kind of hierarchy theorems are there for circuit depth?

Statements like

if $g(n) \in o(f(n))$ and $f(n) \in n^{O(1)}$ then $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq \mathsf{SizeDepth}(n^{O(1)}, f(n))$.

  • 3
    $\begingroup$ Nothing really. We don't know if $\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$ ! $\endgroup$ Oct 9, 2012 at 15:47
  • $\begingroup$ @Kristoffer, yes, that is right, I gave it as an example of the kind of statements I am looking for. In other words interesting classes of circuits where increasing depth is known to make the class larger. $\endgroup$
    – Kaveh
    Oct 9, 2012 at 16:02
  • 2
    $\begingroup$ Am not quite sure, but this should work. We know that the minimum depth of a circuit for $f$ is $\approx$ logarithm of the minimum size of a formula for $f$. Now, the hierarchy for formula size should be possible to show in the same manner as for circuit size (using Shannon-Lupanov results). Say, circuits of size $4t$ are properly stronger than circuits of size $t$. Of course, things get a bit more complicated, if we require the size to be polynomial. $\endgroup$
    – Stasys
    Oct 10, 2012 at 11:52

2 Answers 2


A paper of Klawe, Paul, Pippenger, and Yannakakis gives an hierarchy theorem for constant depth monotone formulas: http://dl.acm.org/citation.cfm?id=808717

Specifically, for every $k$ it gives a function that can be computed by a formula of depth $k$ and size $n$ but requires formulas of depth $k-1$ of size $\exp(n^{1/k})$.


Raz and McKenzie, in Separation of the monotone NC hierarchy, show that the monotone NC hierarchy is strict, and separate monotone NC from monotone P.


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.