Théorèmes de hiérarchie pour la profondeur du circuit

11

Quel genre de théorèmes de hiérarchie existe-t-il pour la profondeur du circuit?

Des déclarations comme

$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
la source

3

Rien vraiment. Nous ne savons pas si

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

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

Kristoffer Arnsfelt Hansen

@ Kristoffer, oui, c'est vrai, je l'ai donné comme exemple du genre de déclarations que je recherche. En d'autres termes, des classes de circuits intéressantes où l'augmentation de la profondeur est connue pour agrandir la classe.

Kaveh

2

Je ne suis pas tout à fait sûr, mais cela devrait fonctionner. Nous savons que la profondeur minimale d'un circuit pour

f

$f$ est

\approx

$\approx$ logarithme de la taille minimale d'une formule pour

f

$f$ . Maintenant, la hiérarchie pour la taille de la formule devrait pouvoir être affichée de la même manière que pour la taille du circuit (en utilisant les résultats de Shannon-Lupanov). Disons que les circuits de taille

4 t

$4t$ sont bien plus résistants que les circuits de taille

t

$t$ . Bien sûr, les choses deviennent un peu plus compliquées, si nous avons besoin que la taille soit polynomiale.

Stasys

8

Un article de Klawe, Paul, Pippenger et Yannakakis donne un théorème de hiérarchie pour les formules monotones à profondeur constante: http://dl.acm.org/citation.cfm?id=808717

Plus précisément, pour chaque il donne une fonction qui peut être calculée par une formule de profondeur et de taille mais nécessite des formules de profondeur de taille . $k$ $k$ $n$ $k-1$ $\exp(n^{1/k})$

Ou Meir
la source

7

Raz et McKenzie, dans Séparation de la hiérarchie NC monotone , montrent que la hiérarchie NC monotone est stricte et sépare NC monotone du monotone P.

Yuval Filmus
la source

Théorèmes de hiérarchie pour la profondeur du circuit

Réponses: