11
$\begingroup$

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

$\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$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.