Teoremas de jerarquía para la profundidad del circuito

11

¿Qué tipo de teoremas de jerarquía existen para la profundidad del circuito?

Declaraciones como

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

cc.complexity-theory circuit-complexity hierarchy-theorems circuit-depth Kaveh
fuente

3

Nada en realidad. ¡No sabemos si !

{N C}^{1} = P / p o l y

$\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$

Kristoffer Arnsfelt Hansen

@ Kristoffer, sí, es cierto, lo di como ejemplo del tipo de declaraciones que estoy buscando. En otras palabras, clases interesantes de circuitos donde se sabe que una profundidad creciente aumenta la clase.

Kaveh

2

No estoy muy seguro, pero esto debería funcionar. Sabemos que la profundidad mínima de un circuito para es logaritmo del tamaño mínimo de una fórmula para . Ahora, la jerarquía para el tamaño de la fórmula debería poder mostrarse de la misma manera que para el tamaño del circuito (usando los resultados de Shannon-Lupanov). Digamos, los circuitos de tamaño son propiamente más fuertes que los circuitos de tamaño . Por supuesto, las cosas se vuelven un poco más complicadas, si requerimos que el tamaño sea polinómico.

f

$f$

\approx

$\approx$

f

$f$

4 t

$4t$

t

$t$

Stasys

8

Un artículo de Klawe, Paul, Pippenger y Yannakakis ofrece un teorema de jerarquía para fórmulas monótonas de profundidad constante: http://dl.acm.org/citation.cfm?id=808717

Específicamente, para cada proporciona una función que puede calcularse mediante una fórmula de profundidad y tamaño pero requiere fórmulas de profundidad de tamaño . $k$ $k$ $n$ $k-1$ $\exp(n^{1/k})$

O meir
fuente

7

Raz y McKenzie, en Separación de la jerarquía monótona de NC , muestran que la jerarquía monótona de NC es estricta, y separan la monótona NC de la monótona P.

Yuval Filmus
fuente

Teoremas de jerarquía para la profundidad del circuito

Respuestas: