Zaawansowane techniki określania dolnych granic złożoności

Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym.

Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby udowodnić dolne granice złożoności problemu w czasie?

W szczególności:

• Jakie są „najnowocześniejsze” techniki opracowane w ostatniej dekadzie?
• Czy można zastosować techniki z algebry abstrakcyjnej, teorii kategorii lub innych gałęzi typowo „czystej” matematyki? (Na przykład często słyszę wzmiankę o „strukturze algebraicznej” sortowania, bez żadnego rzeczywistego wyjaśnienia, co to oznacza).
• Jakie są znaczące, ale mniej znane wyniki dla złożoności dolnej granicy?

Dolne granice obwodów algebraicznych

W ustawieniach obwodów algebraicznych, gdzie dolna granica wielkości obwodu jest analogiczna do dolnej granicy czasu, znanych jest wiele wyników, ale w bardziej nowoczesnych wynikach jest tylko kilka podstawowych technik. Wiem, że prosiłeś o dolne granice czasu, ale myślę, że w wielu przypadkach istnieje nadzieja, że ​​dolne granice algebraiczne pewnego dnia doprowadzą do dolnych granic maszyny Boolean / Turinga. W tych wynikach często stosuje się głębsze techniki z „czystej matematyki”.

I. Stopień związany.

Strassen wykazał, że log stopnia pewnej odmiany algebraicznej powiązanej z funkcją (zestawami) jest dolną granicą rozmiaru obwodu algebraicznego przy obliczaniu tych funkcji.

II. Połączone komponenty (lub bardziej ogólnie wymiar dowolnej wyższej grupy homologii).

Ben-Or pokazał, że rozmiar rzeczywistego drzewa decyzyjnego algebraicznego decydującego o członkostwie w zestawie (półalgebraicznym) wynosi co najmniej gdzie jest liczbą połączonych elementów tego zestawu. Ben-Or wykorzystał to, aby udowodnić dolną granicę sortowania (cóż, odrębność elementu, ale odrębność elementu sprowadza się do sortowania) w prawdziwym algebraicznym modelu drzewa decyzyjnego. Yao rozszerzył to z połączonych komponentów na sumę liczb Bettiego i wykazał optymalne dolne granice dla innych problemów (takich jak equals). W innym artykule Yao rozszerzył to na algebraiczne drzewa decyzyjne ponad liczbami całkowitymi.C Ω ( n log n ) $\log C$$C$$\Omega(n \log n)$$k$

III. Częściowe pochodne.

Był to koń pociągowy wielu współczesnych dolnych granic obwodu algebraicznego. Wierzę, że częściowe pochodne zostały po raz pierwszy użyte do udowodnienia dolnej granicy przez Baura-Strassena, gdzie pokazały, że obliczenie wszystkich pierwszych częściowych można wykonać w rozmiarze gdzie jest rozmiarem potrzebnym do obliczenia . W połączeniu z ograniczeniem stopnia Strassena dawało to rozmiarom dolne granice różnych funkcji, które nadal są najsilniejszymi dolnymi granicami wielkości nieograniczonych obwodów arytmetycznych dla funkcji jawnej.5 s s f Ω ( n log n $f$$5s$$s$$f$$\Omega(n \log n)$

Wydaje się, że nowsze zastosowanie pochodnych cząstkowych wynika z artykułu Nisana, w którym udowodnił on niższe granice w obwodach nieprzemiennych, biorąc pod uwagę wymiar przestrzeni wszystkich pochodnych cząstkowych. Zostało to wykorzystane do udowodnienia niższych granic na ograniczonych rodzajach obwodów głębokości-3 przez Nisana-Wigdersona, a podobne pomysły zostały wykorzystane do udowodnienia niższych granic wielowierszowego rozmiaru formuły przez Raz (i powiązane modele Raz i współpracowników). Niedawne dolne granice głębokości 4 i głębokości 3 Gupty, Kayala, Kamatha i Saptharishi używają uogólnienia tego pomysłu, aby policzyć wymiar przestrzeni „przesuniętych pochodnych cząstkowych” - gdzie można pobrać pochodne cząstkowe, a następnie pomnożyć przez dowolne monomialy danego stopnia. Poprawa wyniku GKKS do super wielomianu dolnej granicy na stałe (co oznaczałoby$\mathrm{VP} \neq \mathrm{VNP}$ ) może „po prostu” być kwestią lepszego zrozumienia ideału generowanego przez permanentnych nieletnich (patrz przypuszczenie na końcu ich artykułu).

IV. Definiowanie równań dla odmian.

Chodzi tutaj o powiązanie z „łatwymi funkcjami” pewnej odmiany algebraicznej, znalezienie równań, które znikają na tej różnorodności, i pokazanie, że równania te nie znikają na „trudnej funkcji”. (Stąd udowadnianie, że twoja trudna funkcja nie jest w szeregu łatwych funkcji, więc jest naprawdę trudna.) Szczególnie przydatne w dolnych granicach mnożenia macierzy. Zobacz Landsberg - Ottaviani na arXiv, aby uzyskać najnowsze informacje i odniesienia do wcześniejszych dolnych granic.

(W rzeczywistości powyższe I, II i III można traktować jako szczególne przypadki znalezienia definicji równań dla niektórych odmian, chociaż dowody, które używają I, II, III, zasadniczo nigdy nie są sformułowane w ten sposób, ponieważ tak naprawdę nie było potrzebować.)

V. Teoria reprezentacji, zwłaszcza jak w teorii złożoności geometrycznej.

Właściwie używany również przez Landsberga - Ottaviani do znalezienia równań dla pewnej odmiany. Używany również przez Burgisser-Ikenmeyer w celu uzyskania „czysto” teoretycznego przedstawienia reprezentacji nieco słabszej dolnej granicy mnożenia macierzy. Przypuszcza się, że Mulmuley i Sohoni (por. „Geometryczna teoria złożoności I i II”) są przydatne do rozwiązania vs i ostatecznie vs. .V N P N P P / p o l $\mathrm{VP}$$\mathrm{VNP}$$\mathrm{NP}$$\mathrm{P/poly}$

Kaveh delikatnie zasugerował w swojej odpowiedzi, że powinienem coś powiedzieć. Nie mam nic więcej do dodania do tej ładnie wyczerpującej listy odpowiedzi. Mogę dodać kilka ogólnych słów o tym, jak kształtowały się dolne granice „złożoności strukturalnej” w ciągu ostatnich dziesięciu lat. (Używam nazwy „złożoność strukturalna” po prostu w celu odróżnienia od algebraicznej, złożoności komunikacyjnej itp.)

Obecne podejścia nadal w dużej mierze opierają się na diagonalizacji, w szczególności na następującym podstawowym paradygmacie: Zacznij od założenia przeciwnego do dolnej granicy. To daje fajny algorytm dla jakiegoś problemu. Spróbuj użyć tego algorytmu, aby zaprzeczyć niektórym twierdzeniom o hierarchii opartym na przekątnej, takim jak hierarchia czasu lub hierarchia przestrzeni. Ponieważ same argumenty diagonalizacji nie wystarczą, aby udowodnić nowe dolne granice, do mieszanki dodaje się inne składniki w celu uzyskania sprzecznej receptury.

Powinienem powiedzieć, że wiele argumentów z lat 70. i 80. można również powiedzieć, że są zgodne z powyższym wzorem; podstawową różnicą w dzisiejszych czasach są „inne składniki” - jest wiele składników do wyboru, a sposoby, w jakie można je nakładać, wydają się być ograniczone tylko przez twoją własną kreatywność. Czasami, gdy nie wiesz, jak mieszać poszczególne składniki, aby uzyskać lepszy przepis, ale bardzo dobrze rozumiesz, jak można je mieszać, pomaga kodować program komputerowy, który sugeruje ci nowe przepisy.

$NEXP \not\subset ACC$

Techniki zależą od modelu i rodzaju zasobów, od których chcemy uzyskać niższą granicę. Zauważ, że aby udowodnić dolną granicę złożoności problemu, musimy najpierw naprawić matematyczny model obliczeń: dolną granicą dla problemu jest to, że żaden algorytm wykorzystujący pewną ilość zasobów nie może rozwiązać problemu, tj. Obliczamy uniwersalnie przez algorytmy. Potrzebujemy matematycznej definicji dziedziny kwantyfikacji. (Zasadniczo dotyczy to wyników niemożności.) Dlatego wyniki w dolnych granicach dotyczą tylko określonego modelu obliczeń. Na przykład$\Omega(n \log n)$dolna granica sortowania działa tylko w przypadku algorytmów sortowania opartych na porównaniu, bez tego ograniczenia i w bardziej ogólnych modelach obliczeń możliwe byłoby rozwiązanie sortowania szybciej, nawet w czasie liniowym. (Zobacz komentarz Josha poniżej.)

Oto kilka podstawowych bezpośrednich metod dowodzenia dolnych granic teorii złożoności obliczeniowej dla bardziej ogólnych modeli obliczeń (maszyny i obwody Turinga).

I. Liczenie:

Pomysł: Pokazujemy, że algorytmów jest więcej funkcji.

Np .: Istnieją funkcje wymagające wykładniczo dużych obwodów.

Problem z tą metodą polega na tym, że jest to argument egzystencjalny i nie daje żadnej wyraźnej funkcji ani żadnej górnej granicy złożoności problemu, który okazał się trudny.

II. Kombinatorialny / Algebraiczny:

Pomysł: Analizujemy obwody i wykazujemy, że mają one określoną właściwość, np. Obliczone przez nie funkcje mogą być aproksymowane przez jakąś ładną klasę obiektu matematycznego, podczas gdy funkcja celu nie ma tej właściwości.

Np .: lemat przełączający Håstad i jego warianty używają drzewa decyzyjnego do przybliżania , Razborov-Smoleński używają wielomianów nad polami do przybliżania funkcji itd. A C 0 [ p $\mathsf{AC^0}$$\mathsf{AC^0}[p]$

Problem z tą metodą polega na tym, że w praktyce działała ona tylko dla małych i stosunkowo łatwych do analizy klas. Istnieje również bariera naturalnych dowodów Razborova-Rudicha, która niejako formalizuje, dlaczego proste właściwości same w sobie raczej nie wystarczą do udowodnienia bardziej ogólnych dolnych granic obwodu.

Artykuł Razborowa „ O metodzie aproksymacji ” dowodzi, że metoda aproksymacji jest kompletna w pewnym sensie do udowodnienia dolnych granic.

III. Diagonalizacja:

Pomysł. Przekątniamy się względem funkcji w mniejszej klasie. Pomysł wraca do Gödela (a nawet Cantora).

Dawny. Czas twierdzenia hierarchii , Przestrzeń hierarchia twierdzenie , etc.

Głównym problemem związanym z tą metodą jest to, że aby uzyskać górną granicę, musimy mieć uniwersalny symulator dla mniejszej klasy i trudno jest znaleźć dobre nietrywialne symulatory. Na przykład, aby oddzielić od , musimy mieć symulator dla wewnątrz a wyniki wskazują, że jeśli są takie symulatory, to nie będą bądź miły. Dlatego zwykle kończymy rozdzielaniem klas o tym samym typie zasobów, gdzie przy odrobinie większej ilości zasobów możemy ogólnie symulować mniejszą klasę.P S p a c e P P S p a c $\mathsf{P}$$\mathsf{PSpace}$$\mathsf{P}$$\mathsf{PSpace}$

Mamy także barierę relatywizacji (wracając do Bakera, Gilla i Solovaya) i barierę algebraizacji (autorstwa Aaronsona i Wigdersona), które stwierdzają, że poszczególne typy argumentów diagonalizacji zostaną przeniesione do innych ustawień, w których wynik jest prawdopodobnie fałszywy.

Należy zauważyć, że bariery te nie dotyczą bardziej ogólnych argumentów diagonalizacji. W rzeczywistości, w pracy Dextera Kozen'a „ Indeksowanie klas subrekursywnych ”, diagonalizacja jest zakończona dla udowodnienia dolnych granic.

Jak zapewne zauważyliście, istnieje silna zależność między znalezieniem dobrych uniwersalnych symulatorów dla klasy złożoności a oddzieleniem tej klasy złożoności od klas większych (formalne oświadczenie znajduje się w pracy Kozen).

Ostatnie prace

Najnowsze postępy można znaleźć w ostatnich artykułach Ryana Williamsa . Nie omawiam ich w tej odpowiedzi, ponieważ mam nadzieję, że sam Ryan napisze odpowiedź.

Algebraiczne drzewa decyzyjne

To nie jest nowa technika, ale dość potężna w przypadku niektórych problemów.

Algebraiczny model drzewa decyzyjnego stanowi potężną generalizację drzew porównawczych. W tym modelu algorytm jest modelowany jako niejednorodna rodzina drzew decyzyjnych, po jednym dla każdego rozmiaru wejściowego . Konkretnie, th-order drzewo algebraiczne decyzja jest zakorzenione trójargumentowy drzewo o następującej strukturze:$n$$d$

• Każdy węzeł inny niż liść jest oznaczony wielomianowym wielomianowym zapytaniem stopnia co najwyżej . Na przykład w drzewie porównania każdy wielomian zapytania ma postać dla niektórych indii i .q v ( x 1$v$$q_v(x_1, \dots, x_n)$$d$$x_i-x_j$$i$$j$

• Krawędzie opuszczające każdy węzeł inny niż liść są oznaczone jako , i .$-1$$0$$+1$

• Każdy liść jest oznaczony możliwym opisem wyjściowym. Na przykład w przypadku problemu z sortowaniem każdy liść jest oznaczony permutacją zestawu . W przypadku problemów decyzyjnych każdy liść jest oznaczony „tak” lub „nie”.$\{1,2,\dots,n\}$

Biorąc pod uwagę wektor wejściowy , wykonujemy obliczenia, przechodząc przez ścieżkę w dół od katalogu głównego, rozgałęziając się zgodnie ze znakiem wielomianów zapytania w odwiedzanych węzłach. Podróż ostatecznie dociera do liścia; etykieta tego liścia jest wynikiem. „Czas działania” algorytmu jest definiowany jako długość przemierzonej ścieżki; dlatego najgorszym czasem działania jest głębokość drzewa decyzyjnego.$\vec{x}\in\mathbb{R}^n$

W szczególności zauważ, że każdy wielomian zapytania może mieć odrębne terminy; niemniej jednak model zakłada, że ​​możemy oceniać znak dowolnego wielomianu zapytania w stałym czasie.$\Omega(n^d)$

Dla każdego liścia , niech oznacza zbiór wektorów wejściowych, dla których wykonanie sięga . Z konstrukcji jest częściowo algebraicznym podzbiorem zdefiniowanym przez co najwyżej nierówności wielomianowe stopnia co najwyżej , dla niektórych stałych . Klasyczne twierdzenie niezależnie udowodnione przez Pietrowskiego i Oleszcznika, Thoma i Milnora sugeruje, że taki zestaw półalgebraiczny ma co najwyżej elementy.R ( ℓ ) ⊆ R n ℓ R ( ℓ ) R n t = głębokość ( ℓ ) d d ( d t ) O ( n $\ell$$R(\ell) \subseteq \mathbb{R}^n$$\ell$$R(\ell)$$\mathbb{R}^n$$t = \text{depth}(\ell)$$d$$d$$(dt)^{O(n)}$

$W\subseteq\mathbb{R}^n$$d$$t$$W$$3^t (dt)^{O(n)}$$t = \Omega(\log \#W - n\log d)$

$n$$W$$n!$$n$$\Omega(n\log n)$

$\Omega(n\log n)$

$R(\ell)$$(dt)^{O(n)}$

$n^{O(n)}$$n\log n$

$\Omega(n^2)$$O(n^4\log n)$$2^{O(n)}$$\mathbb{R}^n$$n^4\log n$$k$$k$$k$$k$$O(n^{k/2})$$O(n^4\log n)$wielomiany zapytań; ten czas budowy jest bezpłatny w modelu z dolną granicą.

Brawo dla podwójnie negatywnych wyników!

Manindra Agrawal ma ładny artykuł „Udowadnianie dolnych granic poprzez generatory Psuedorandom”. Można to uznać za „ciemnego konia” w biegu, aby udowodnić dolne granice, ale papier jest interesujący.

jest to ankieta 32p, która właśnie pojawiła się na tym temacie, skupiając się na kącie dolnych granic obwodu (tutaj treść mocno pokrywa się z innymi odpowiedziami).

• Algorytmy kontra obwody dolne według Oliveiry

Zastosowano różne techniki, aby udowodnić kilka twierdzeń o przeniesieniu postaci „nietrywialne algorytmy dla obwodu wydajności klasy C dolnej granicy dla C”. W tej ankiecie ponownie przeglądamy wiele z tych wyników. Omawiamy, w jaki sposób można uzyskać dolne granice obwodu z algorytmów derandomizacji, kompresji, uczenia się i satysfakcji. Obejmujemy także związek między dolnymi granicami obwodu a użytecznymi właściwościami, które okazują się fundamentalne w kontekście tych twierdzeń o przeniesieniu. Po drodze otrzymujemy kilka nowych wyników, upraszczamy kilka dowodów i pokazujemy połączenia obejmujące różne frameworki. Mamy nadzieję, że nasza prezentacja będzie stanowić samodzielne wprowadzenie dla osób zainteresowanych prowadzeniem badań w tej dziedzinie.