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))$.
11
$\begingroup$
$\endgroup$
-
3$\begingroup$ Nothing really. We don't know if $\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$ ! $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 9 '12 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 '12 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 '12 at 11:52
8
$\begingroup$
$\endgroup$
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})$.
7
$\begingroup$
$\endgroup$
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.
answered Oct 10 '12 at 3:47
