Algorytmy i teoria złożoności strukturalnej

Wiele ważnych wyników w teorii złożoności obliczeniowej, a zwłaszcza teoria złożoności „strukturalnej”, ma interesującą właściwość, którą można rozumieć jako zasadniczo wynikającą (jak widzę ...) z wyników algorytmicznych, dającą skuteczny algorytm lub protokół komunikacyjny dla niektórych problem. Należą do nich:

IP = PSPACE wynika z wydajnego przestrzennie algorytmu rekurencyjnego symulującego interaktywne protokoły oraz wydajnego interaktywnego protokołu do oceny całkowicie skwantyfikowanych formuł boolowskich. W rzeczywistości każda równość klasy złożoności A = B może być postrzegana jako wynikająca z dwóch wydajnych algorytmów (algorytm dla problemów w A, który jest wydajny w odniesieniu do B i odwrotnie).
Udowodnienie kompletności NP jakiegoś problemu to po prostu znalezienie wydajnego algorytmu, który zredukuje do niego problem NP-zupełności.
(Prawdopodobnie!) Kluczowym składnikiem twierdzenia o hierarchii czasu jest wydajna uniwersalna symulacja maszyn Turinga.
$\not \supset$
PCP Twierdzenie to, że efektywne wzmocnienie luka jest możliwe ograniczenie problemów satysfakcji.
itd itd.

Moje pytanie (które może być beznadziejnie niejasne!) Brzmi następująco: Czy są jakieś ważne wyniki w teorii złożoności strukturalnej (w odróżnieniu od „meta-wyników”, takich jak bariera relatywizacji), o których nie wiadomo, że mają naturalną interpretację pod względem wydajności algorytmy (lub protokoły komunikacyjne)?

cc.complexity-theory structural-complexity

— Ashley Montanaro
źródło

Mam nadzieję, że odpowiedź brzmi „nie”, ponieważ uważam, że złożoność polega na zrozumieniu mocy algorytmów! Chciałem powiedzieć, że PARITY nie w prawie się kwalifikuje, ale teraz nie sądzę. Można zobaczyć Switching Lemat jak randomizowanym algorytm, który pozwala zamienić dwa rzędy obwodzie bez dużego rozmiaru blow-up (i to nawet może być derandomized ( eccc.hpi-web.de/report/2012/116 ).

A C^{0}

$AC^0$

— Joshua Grochow

AshleyMontanaro: Być może teoria złożoności jest „z definicji” powiązana z wydajnością algorytmów (czas / przestrzeń). Gdy tylko odejdziesz od wydajności, znajdziesz podstawowe wyniki, takie jak nierozstrzygalność problemu zatrzymania, ale nie jesteś już w dziedzinie „złożoności”. Jednak próbując dać częściową odpowiedź, myślę, że charakterystyka logiczna klas złożoności jest ważnym rezultatem, który daje inną perspektywę niezwiązaną (bezpośrednio) z „algorytmami”.

— Marzio De Biasi,

W szczególności wymieniłbym opisową charakterystykę NP pod względem egzystencjalnej logiki drugiego rzędu. Chodzi tu wyłącznie o siłę ekspresji i nie dotyczy przede wszystkim algorytmów. Twierdzenie Courcelle'a sugeruje jednak, że to rozróżnienie nie jest prawdziwe.

— Suresh Venkat

Czy powiedziałbyś, że dowód PARYBORA Razborowa-Smoleńskiego, którego nie ma w AC0, zawiera wynik algorytmiczny? A co z dolnymi granicami złożoności zapytań, takimi jak te, które mówią, że komputer kwantowy nie może rozwiązać problemu nieuporządkowanego wyszukiwania w zapytaniach ?

o (\sqrt{n})

$o(\sqrt{n})$

— Robin Kothari,

patrz także cstheory.stackexchange.com/questions/3229/…

— sdcvvc

Dla wielu niższych granic złożoności algebraicznej nie znam naturalnej interpretacji pod względem wydajnych algorytmów. Na przykład:

technika cząstkowych pochodnych Nisana i Wigdersona
technika rangowa Hesji według Mignona i Ressayre'a (dająca obecnie najlepiej znaną dolną granicę wyznacznika permanentnego kontra wyznacznik)
stopień naukowy Strassena (i Baura-Strassena)
technika połączonych komponentów Ben-Or.

We wszystkich powyższych wynikach naprawdę wydają się wykorzystywać właściwość zaangażowanych funkcji, przy czym sama właściwość wydaje się niezwiązana z istnieniem jakiegokolwiek konkretnego algorytmu (nie mówiąc już o efektywnym).

Aby uzyskać wyniki niealgebraiczne, oto kilka myśli:

Standardowy argument liczenia dla dolnej granicy sortowania nie wydaje się mieć interpretacji pod względem wydajnych algorytmów. Istnieje jednak przeciwna wersja tej dolnej granicy [1], w której istnieje algorytm, który przy dowolnym drzewie decyzyjnym, które wykorzystuje zbyt mało porównań, skutecznie tworzy listę, którą drzewo decyzyjne sortuje niepoprawnie. Ale wersja przeciwna, choć nie trudna, jest znacznie trudniejsza niż dowód liczenia. (Zauważ, że jest to nieco silniejsze niż to, co można uzyskać przez zastosowanie techniki dolnej granicy przeciwnika, np. Jak w tych notatkach , ponieważ w [1] sam przeciwnik jest skuteczny .) $n \log n$
Myślę, że zmieniłem zdanie na temat PARYSTII nie w (nawet oryginalny dowód, nie mówiąc już o dowodzie Razborowa-Smoleńskiego, jak wskazał @RobinKothari). Chociaż przełączającą lematę można postrzegać jako algorytm losowy ( lub deterministyczny ), który pozwala zamienić dwa rzędy obwodu bez dużego powiększenia, myślę, że to naprawdę ma inny smak niż wiele rezultatów złożoności, a konkretnie te, które cytujesz. Na przykład dowód Williamsa, że opiera się zasadniczo na istnieniu dobrego algorytmu dla konkretnego problemu. W przeciwieństwie do tego, jeśli ktoś mógłby udowodnić coś w sposób niekonstruktywny niż Lemat Przełączająca, byłoby to równie dobre dla udowodnienia PARYMACJI poza . $AC^0$ $ACC \neq NEXP$ $AC^0$

Z powodu tych dwóch ostatnich przykładów - zwłaszcza sortowania, w których standardowy dowód nie jest konstruktywny - wydaje mi się, że pytanie może dotyczyć nie tylko naturalnych interpretacji w zakresie wydajnych algorytmów, ale także w jakiś sposób konstruktywności / skuteczności dowodów różnych wyniki złożoności (w zależności od tego, co miał na myśli PO). Oznacza to, że dolna granica sortowania standardowego nie jest konstruktywna ani algorytmiczna, ale istnieje konstruktywny, algorytmiczny dowód tego samego wyniku.

[1] Atallah, MJ i Kosaraju, SR Dolna granica sortowania oparta na przeciwnikach . Poinformować. Proc. Łotysz. 13 (2): 55–57, 1981.

— Joshua Grochow
źródło