Dolne granice dla formuł o stałej głębokości?

21

Wiemy dużo o ograniczeniach obwodów o stałej głębokości (rozmiar wielomianowy). Ponieważ formuły o stałej głębokości (rozmiar wielomianowy) są jeszcze bardziej ograniczonym modelem obliczeń, wszystkie problemy, o których wiadomo, że nie występują w AC ^0, również nie są obliczalne na podstawie wzoru o stałej głębokości. Ponieważ jednak jest to łatwiejszy model, domyślam się, że w tym modelu jest więcej problemów, których nie da się obliczyć. Czy zostało to zbadane? (Zgaduję, że tak było, ale prawdopodobnie nie używam odpowiednich wyszukiwanych haseł).

Konkretnie Jestem zainteresowany następującym pytaniem: Czy jest jakaś funkcja f, które mogą być obliczane przez AC ⁰ obwodzie rozmiarze S, ale potrzebuje wzoru stałej głębokości rozmiarze przynajmniej Quadratic w S, lub super-wielomian w S? Jaki jest najbardziej znany wynik tego rodzaju?

W przypadku, gdy nie jest jasne, co rozumiem przez formułę o stałej głębokości, mam na myśli formułę, która jeśli wypiszesz jako drzewo (z wewnętrznymi węzłami będącymi bramkami AND / OR / NOT, a liśćmi wejściowymi), to drzewo ma stałą wysokość. Równolegle formuła o stałej głębokości jest obwodem o stałej głębokości, w którym wszystkie bramki niepochodzące mają fanout 1.

cc.complexity-theory circuit-complexity lower-bounds Robin Kothari
źródło

11

Łatwo przekonwertować obwód o stałej głębokości na formułę stałej głębokości o tej samej głębokości ze wzrostem wielkości wielomianu, wykonując kopie bramek używanych więcej niż raz. Jeśli głębokość obwodu wynosi a jego rozmiar to , wzór będzie miał głębokość i rozmiar . Dlatego odpowiedź brzmi nie. $d$ $O(p(n))$ $d$ $O((p(n))^d)$

Kaveh
źródło

5

daje to więcej niż kwadratowy wzrost wielkości. (Oczywiście, nie wzrost super-wielomianowy.)

Iddo Tzameret

2

Dziękuję za odpowiedź. Masz pojęcie o konkretnej funkcji f, która ma obwód o stałej głębokości o rozmiarze S, ale potrzebuje formuły o rozmiarze S ^ 2 lub S ^ 10 itd.?

Robin Kothari,

3

Myślę, że relacja między głębokością a rozmiarem obwodu jest wciąż otwarta (wiadomo, że „głębokość” to teta wielkości formuły). Zobacz rozdziały 7 i 8 w książce Wegenera „Złożoność funkcji boolowskich”, aby uzyskać informacje na temat niektórych funkcji z wyraźnymi dolnymi granicami wielkości formuły. Jest taki, który ma prawie kwadratowy wzrost (

), nie zauważył nic lepszego.

n^{2} / l o g n

$n^2/log n$

Kaveh

17

To pytanie zostało całkowicie rozwiązane (aż do stałych czynników) dzięki niedawnemu wynikowi Benjamina Rossmana ( http://eccc.hpi-web.de/report/2013/169/ ).

Jak wskazuje Kaveh powyżej, obwód , rozmiar , obwód można przekształcić na wzór , rozmiar . $d$ $S$ $d$ $S^d$

Rossman pokazuje, że jest to zasadniczo ciasne. Dla każdej głębokości , wykazuje on funkcję, która może być obliczana przez obwód o stałej głębokości głębokość i wielkość , ale dowolny wzór stałej głębokości (lub nawet $d$ $d$ $S = O(n^3)$ -formuła głębokości) potrzebuje rozmiaru aby go obliczyć. $\sqrt{\log n}$ $S^{\Omega(d)}$

(Zapomniałem powiedzieć to wcześniej: Podziękowania dla Benjamina Rossmana za poinformowanie mnie o tym wyniku).

Robin Kothari
źródło

Dolne granice dla formuł o stałej głębokości?

Odpowiedzi: