Hierarchiesätze für die Schaltungstiefe

11

Welche Art von Hierarchiesätzen gibt es für die Schaltungstiefe?

Aussagen wie

wenn und dann ist $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
quelle

3

Nichts wirklich. Wir wissen nicht, ob

!

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

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

Kristoffer Arnsfelt Hansen

@Kristoffer, ja, das ist richtig, ich habe es als Beispiel für die Art von Aussagen gegeben, nach denen ich suche. Mit anderen Worten, interessante Klassen von Schaltungen, bei denen bekannt ist, dass eine zunehmende Tiefe die Klasse größer macht.

Kaveh

2

f

$f$

\approx

$\approx$

f

$f$

4 t

$4t$

t

$t$

8

Ein Artikel von Klawe, Paul, Pippenger und Yannakakis enthält einen Hierarchiesatz für monotone Formeln mit konstanter Tiefe: http://dl.acm.org/citation.cfm?id=808717

$k$ $k$ $n$ $k-1$ $\exp(n^{1/k})$

Oder Meir
quelle

7

Raz und McKenzie zeigen in Trennung der monotonen NC-Hierarchie , dass die monotone NC-Hierarchie streng ist, und trennen monotone NC von monotonen P.

Yuval Filmus
quelle

Hierarchiesätze für die Schaltungstiefe

Antworten: