Teoremas da hierarquia para profundidade do circuito

11

Que tipo de teoremas de hierarquia existem para a profundidade do circuito?

Declarações 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
fonte

3

Nada realmente. Não sabemos se

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

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

Kristoffer Arnsfelt Hansen

@ Kristoffer, sim, isso mesmo, dei como exemplo do tipo de declaração que estou procurando. Em outras palavras, classes interessantes de circuitos em que o aumento da profundidade é conhecido por aumentar a classe.

Kaveh

2

Não tenho muita certeza, mas isso deve funcionar. Sabemos que a profundidade mínima de um circuito para

f

$f$ é

\approx

$\approx$ logaritmo do tamanho mínimo de uma fórmula para

f

$f$ . Agora, é possível mostrar a hierarquia para o tamanho da fórmula da mesma maneira que para o tamanho do circuito (usando os resultados de Shannon-Lupanov). Digamos, circuitos de tamanho

4 t

$4t$ são adequadamente mais fortes que circuitos de tamanho

t

$t$ . Obviamente, as coisas ficam um pouco mais complicadas, se exigirmos que o tamanho seja polinomial.

Stasys

8

Um artigo de Klawe, Paul, Pippenger e Yannakakis fornece um teorema da hierarquia para fórmulas monótonas de profundidade constante: http://dl.acm.org/citation.cfm?id=808717

Especificamente, para cada ela fornece uma função que pode ser calculada por uma fórmula de profundidade tamanho mas requer fórmulas de profundidade de tamanho . $k$ $k$ $n$ $k-1$ $\exp(n^{1/k})$

Ou Meir
fonte

7

Raz e McKenzie, em Separação da hierarquia NC monótona , mostram que a hierarquia NC monótona é rigorosa e separam NC monótona da monótona P.

Yuval Filmus
fonte

Teoremas da hierarquia para profundidade do circuito

Respostas: