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)?

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.