Twierdzenia o hierarchii głębokości obwodu

11

Jakie są twierdzenia dotyczące hierarchii głębokości obwodu?

Oświadczenia takie jak

jeśli i to $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
źródło

3

Nic takiego. Nie wiemy, czy

!

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

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

Kristoffer Arnsfelt Hansen

@Kristoffer, tak, zgadza się, podałem to jako przykład rodzaju stwierdzeń, których szukam. Innymi słowy, interesujące klasy obwodów, o których wiadomo, że zwiększenie głębokości powoduje powiększenie klasy.

Kaveh

2

Nie jestem do końca pewien, ale to powinno działać. Wiemy, że minimalna głębokość obwodu dla

wynosi

logarytm minimalnej wielkości wzoru na

. Teraz hierarchia wielkości formuły powinna być możliwa do pokazania w taki sam sposób, jak dla wielkości obwodu (przy użyciu wyników Shannona-Lupanova). Powiedzmy, że obwody o rozmiarze

są odpowiednio silniejsze niż obwody o rozmiarze

. Oczywiście sytuacja się komplikuje, jeśli wymagamy wielomianu.

f

$f$

\approx

$\approx$

f

$f$

4 t

$4t$

t

$t$

Stasys,

8

Artykuł Klawe, Paula, Pippengera i Yannakakisa podaje twierdzenie o hierarchii dla formuł monotonicznych o stałej głębokości: http://dl.acm.org/citation.cfm?id=808717

W szczególności, dla każdego daje funkcję, którą można obliczyć za pomocą wzoru głębokości i wielkości ale wymaga wzorów głębokości wielkości . $k$ $k$ $n$ $k-1$ $\exp(n^{1/k})$

Lub Meir
źródło

7

Raz i McKenzie w rozdziale Separacja monotonicznej hierarchii NC pokazują, że monotoniczna hierarchia NC jest ścisła, i oddzielają monotoniczny NC od monotonicznego P.

Yuval Filmus
źródło

Twierdzenia o hierarchii głębokości obwodu

Odpowiedzi: