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

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

CC BY-SA 3.0
2012-10-10T03:06:24.223Z
2012-10-10T03:06:24.223Z
Or Meir
<p>Raz and McKenzie, in <a href="http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmonotone.ps">Separation of the monotone NC hierarchy</a>, show that the monotone NC hierarchy is strict, and separate monotone NC from monotone P.</p>

CC BY-SA 3.0
2012-10-10T03:47:13.460Z
2012-10-10T03:47:13.460Z
Yuval Filmus
<p>What kind of hierarchy theorems are there for circuit depth?</p>

<p>Statements like</p>

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

CC BY-SA 3.0
2012-10-09T15:47:12.043Z
Nothing really. We don't know if $\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$ !
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-10-09T16:02:29.683Z
@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.
Kaveh
CC BY-SA 3.0
2012-10-10T11:52:19.030Z
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.
Stasys
<cc.complexity-theory><circuit-complexity><hierarchy-theorems><circuit-depth>
Hierarchy theorems for circuit depth
Kaveh
# Hierarchy theorems for circuit depth

(Asked by: username_0 on 2012-10-09)

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

**Tags:** cc.complexity-theory, circuit-complexity, hierarchy-theorems, circuit-depth
> **Comments:**
> **username_1**: Nothing really. We don't know if $\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$ !  
> **username_0**: @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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_3 on 2012-10-10. Score: 8

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


---

### Answer by username_4 on 2012-10-10. Score: 7

Raz and McKenzie, in [Separation of the monotone NC hierarchy](http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmonotone.ps), show that the monotone NC hierarchy is strict, and separate monotone NC from monotone P.


---

