Status w dolnych granicach obwodu dla obwodów głębokości ograniczonych przez polilog

Złożoność obwodu złożoności jest jednym z głównych obszarów badań w ramach teorii złożoności obwodu. Ten temat ma swoje początki w wynikach takich jak „funkcja parzystości nie jest w ” i „funkcja mod nie jest obliczana przez ”, gdzie jest klasą języków rozstrzygalnych na podstawie niejednolitej, stałej głębokości, wielomianu, nieograniczonego wachlarza bramek AND, OR, NOT i modulo , gdzie . Wydaje się jednak, że uzyskanie konkretnych wyników w dolnych granicach w polilogarytmicznych obwodach głębokości jest nieosiągalne przy użyciu klasycznych metod, takich jak ograniczanie danych wejściowych i przybliżanie wielomianów na polach skończonych.$AC^{0}$$p$$AC^{0}[q]$$AC^0[q]$$q$$\gcd(p,q)=1$

Znam pracę STOC'96, która prowadzi do teorii złożoności geometrycznej i która pokazuje, że wydajne obliczenia równoległe przy użyciu operacji bez operacji bitowych nie są w stanie obliczyć problemu minimalnego przepływu.

Oznacza to, że w niektórych ograniczonych ustawieniach możemy udowodnić dolne granice $NC$ dla niektórych problemów z $P$ ukończeniem.

Po pierwsze, czy istnieją inne metody lub techniki, które mogą być wiarygodnym podejściem do udowodnienia dolnych granic obwodu głębokości polilogarytmicznej?

Po drugie, jak przydatne jest następujące stwierdzenie dla społeczności teorii?

Rozmiar obwodu $NC$ obliczającego funkcję boolowską $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ wynosi co najmniej $l$ , gdzie $l$ jest pewną wielkością matematyczną zależną od twardości funkcja celu $f$ . Wartość $l$ może być na przykład wielkością kombinatoryczną, taką jak rozbieżność, liniową wielkością algebraiczną, taką jak ranga pewnego rodzaju macierzy nad polem, lub jakąś zupełnie nową wielkością, która nie była wcześniej stosowana w teorii złożoności.

W przypadku technik udowadniania dolnych granic obwodu poliglogu wszystkie obecne podejścia działają w ograniczonych ustawieniach. Podobnie jak w pracy prowadzącej do GCT , o której wspominasz, dolna granica dotyczy ograniczonego modelu PRAM bez operacji bitowych.

Pod innym ograniczeniem, jakim jest monotoniczne ograniczenie dla monotonicznych funkcji boolowskich, istnieje podejście Fouriera-analityczne (lub liczbowo-kombinatoryczne) do udowodnienia dolnych granic obwodu monotonicznego, w mojej wspólnej pracy z Aaronem Potechinem ( ECCC i STOC ). Poprawia to wcześniejsze wyniki Ran Raz i Pierre'a McKenziego, które rozszerzają ramy gry komunikacyjnej Mauricio Karchmera i Avi Wigderson o głębokość obwodu.

Scott Aaronson i Avi Wigderson zaproponowali kolejną linię badań nad rozszerzeniem gry Karchmer – Wigderson jako poleconą grę komunikacyjną , której rozszerzenie do protokołu rywalizującego dowodzenia jest sugerowane jako podejście do oddzielenia NC od P przez Gillata Kola i Ran Raza ( ECCC i ITCS ).

Oprócz badania syntaktycznego ograniczenia monotoniczności, istnieje podejście do badania ograniczenia semantycznego związanego z grami kamykowymi (zwanymi oszczędnymi programami rozgałęziającymi) autorstwa Stephena Cooka, Pierre'a McKenziego, Dustina Wehra, Marka Bravermana i Rahula Santhanama. Istnieje silna dolna granica pod oszczędnym ograniczeniem Dustina Wehra, odpowiadająca najlepiej znanej górnej granicy dla problemów z P-zupełnością. Wyniki te dotyczą złożoności deterministycznej przestrzeni, która obniża granice czasu równoległego lub głębokości obwodu przez znane wyniki symulacji (np. Od ).$\text{AlternatingTime}[t] \subseteq \text{DeterministicSpace}[t]$

Jeśli chodzi o pytanie dotyczące wielkości i głębokości obwodów, można zastosować następujące podejście. Richard Lipton i Ryan Williams pokazują, że biorąc pod uwagę wystarczająco silną dolną granicę głębokości (tj. ), dolna granica słabego rozmiaru (tj. ) może oddziel NC od P. Wynik ten wynika z argumentu kompromisu dotyczącego głębokości opartego na symulacjach dotyczących bloku. Wcześniejszy wynik dotyczący głębokości handlu wielkością jest spowodowany przez Allendera i Koucký'ego w oparciu o ideę samoodwracalności, ale badał mniejsze klasy złożoności, takie jak NC i NL.$n^{1-O(1)}$$n^{1+\Omega(1)}$$^1$

Należy zauważyć, że spośród wyżej wymienionych podejść niektóre z nich uwzględniają zarówno rozmiar, jak i głębokość obwodów, podczas gdy inne podejścia uwzględniają tylko głębokość obwodu. W szczególności częściowo algebro-geometryczne podejście Mulmuleya , protokół rywalizującego provera badany przez Kol-Raza oraz podejście kompromisu między głębokością a wielkością Allendera-Kouckégo i Liptona-Williamsa dotyczą zarówno wielkości, jak i głębokości obwodów. Wyniki w Chan – Potechin , Raz – McKenzie , Cook – McKenzie – Wehr – Braverman – Santhanam i Wehr dają dolne granice obwodu przy ograniczonych ustawieniach niezależnie od wielkości. Również wspomniana gra komunikacyjna zAaronson – Wigderson dotyczy tylko głębokości obwodu.

Nadal jest zgodny z naszą wiedzą, że niektóre problemy z kompletnym P nie mogą być obliczone przez obwody o małej głębokości (tj. ), niezależnie od wielkości. Jeśli rozmiar nie ma znaczenia dla obwodów o małej głębokości (ograniczonego wachlowania), być może warto skoncentrować się bardziej na głębokości obwodu niż na rozmiarze obwodów o małej głębokości.$\log^{O(1)}n$

Zgodnie z sugestią Kaveha, zamieszczam swój komentarz jako (rozszerzoną) odpowiedź.

Jeśli chodzi o $Q1$ , należy zachować ostrożność: nawet głębokość logarytmiczna, jeśli jest daleka od zrozumienia, nie mówiąc już o polilarytmice. Tak więc w świecie niemonotonicznym prawdziwy problem jest znacznie mniej ambitny:

Pokonanie głębokości kłody Problem: Udowodnij superliniową (!) Dolną granicę dla obwodów . $NC^1$

Problem pozostaje otwarta (do tej pory ponad 30 lat), nawet o liniowym -circuits. Są to obwody Fanin- 2 na podstawie { ⊕ , 1 } i obliczają transformacje liniowe f ( x ) = A x powyżej G F ( 2 ) . Łatwe liczenie pokazuje, że prawie wszystkie macierze A wymagają bramek Ω ( n 2 / log n ) , na dowolnej głębokości. $NC^1$$2$$\{\oplus,1\}$$f(x)=Ax$$GF(2)$$A$$\Omega(n^2/\log n)$

Odnośnie $Q2$ : Tak, możemy mieć pewne algebraicznych / środki combinatoric, niższe granice na który bił obwodów dziennika głębokości. Niestety, jak dotąd, nie możemy udowodnić wystarczająco dużych ograniczeń tych środków. Załóżmy na liniowy -circuits, taki środek jest sztywność R ( R ) macierzy A . Jest to najmniejsza liczba pozycji A , którą należy zmienić, aby obniżyć rangę do r . Łatwo jest wykazać, że R A ( r ) ≤ ( n $NC^1$ $R_A(r)$$A$$A$$r$ blokady dla każdej boolean n × n macierzy A , a Valiant (1977) wykazał, że ta granica jest ścisła dla prawie wszystkich macierzy. Aby pokonać obwodów dziennika głębokość, wystarczy wykazują sekwencji logicznej n x n macierzytak, że$R_A(r)\leq (n-r)^2$$n\times n$$A$$n\times n$$A$

dla stałych ϵ , δ > 0 . $R_A(\epsilon n)\geq n^{1+\delta}$$\epsilon,\delta>0$

Do tej pory najlepiej znamy macierze z R A ( r ) ≥ ( n 2 / r ) log ( n / r ) . Dla matryc Sylvester (tj wewnętrzne matryce produktu), przy czym dolna granica Ohm ( n 2 / r ), to łatwo wykazać . $A$$R_A(r)\geq (n^2/r)\log(n/r)$$\Omega(n^2/r)$

Mamy kombinatorycznych środki do ogólnego (nieliniowe) -circuits, a przypadku dwuczęściowego n x n grafu G , niech t ( G ) jest najmniejsza liczba T tak, że G może być zapisana jako skrzyżowaniu T dwudzielny wykresy, z których każdy stanowi połączenie co najwyżej t kompletnych wykresów dwustronnych. Aby pokonać ogólne obwody głębokości logów, wystarczy znaleźć sekwencję wykresów$NC^1$$n\times n$$G$$t(G)$$t$$G$$t$$t$

dla stałej ϵ > $t(G_n)\geq n^{\epsilon}$$\epsilon >0$

(patrz np. tutaj, jak to się dzieje). Ponownie, prawie wszystkie mają wykresy . Jednak najlepsza pozostaje dolna granica t ( G ) ≥ log 3 n dla matryc Sylvester, ze względu na Lokama . $t(G)\geq n^{1/2}$$t(G)\geq \log^3 n$

Na koniec pozwól mi wspomnieć, że mamy nawet „prostą” kombinatoryczną miarę (ilość) słabą (liniową) dolną granicę, która dałaby nawet wykładnicze (!) Dolne granice dla obwodów niemonotonowych. Dla dwustronnego wykresu G , niech c ( G ) będzie najmniejszą liczbą operacji łączenia przez fanin- 2 ( ∪ ) i przecięcia ( ∩ ) wymaganych do wytworzenia G, gdy zaczynamy od gwiazd; gwiazda to zestaw krawędzi łączących jeden wierzchołek ze wszystkimi wierzchołkami po drugiej stronie. Prawie wszystkie wykresy mają c ( G ) = Ω ( n $n\times n$$G$$c(G)$$2$$\cup$$\cap$$G$ . Z drugiej strony, dolna granica$c(G)=\Omega(n^2/\log n)$

o stałej ε > $c(G_n)\geq (4+\epsilon)n$$\epsilon>0$

Oznaczałoby to dolna granica w obwodzie złożoność niż monotonicznej wyraźnego logicznej funkcji f G z N zmiennych. Jeśli G jest n × m wykresem przy m = o ( n ) , to wystarczy nawet dolna granica c ( G n ) ≥ ( 2 + ϵ ) n (ponownie, patrz np. Tutaj, jak to się dzieje). Dolne granice c ( $\Omega(2^{N/2})$$f_G$$N$$G$$n\times m$$m=o(n)$$c(G_n)\geq (2+\epsilon)n$ można wyświetlić dla stosunkowo prostych wykresów. Problem polega jednak na tym, aby „ - ϵ ” zastąpić „ + ϵ ”. Więcej kombinatorycznych środków o niższej złożoności obwodu (w tym obwodów A C C ) można znaleźć w książce. $c(G)\geq (2-\epsilon)n$$-\epsilon$$+\epsilon$$ACC$

$2+\epsilon$$P\neq NP$$c(G)$dolna granica: pewna klasa złożoności zawiera funkcję wymagającą dużych obwodów lub wzorów. Ale ostatecznym celem jest wymyślenie wyraźnej twardej funkcji, której definicja nie ma „zapachu algorytmicznego”, nie ma żadnych ukrytych aspektów złożoności.