Zaskakujące wyniki w złożoności (nie na liście blogów złożoności)

Jakie były najbardziej zaskakujące wyniki w złożoności?

Myślę, że przydałaby się lista niespodziewanych / zaskakujących wyników. Obejmuje to zarówno zaskakujące wyniki, które pojawiły się znikąd, jak i wyniki, które okazały się inne niż oczekiwano.

Edycja : biorąc pod uwagę listę Gasarcha, Lewisa i Ladnera na blogu złożoności (wskazanym przez @Zeyu), skupmy się na tej wiki społeczności na wynikach, których nie ma na ich liście. Być może doprowadzi to do skupienia się na wynikach po 2005 r. (Zgodnie z sugestią @ Jukki).

Przykład: Słabe uczenie = mocne uczenie się [Schapire 1990] : (Zaskakująco?) Posiadanie przewagi nad przypadkowymi zgadywaniami pozwala na naukę PAC. Poprowadź do algorytmu AdaBoost.

Oto post gościnny Billa Gasarcha z pomocą Harry'ego Lewisa i Richarda Ladnera: http://blog.computationalcomplexity.org/2005/12/surishing-results.html

Jeśli , istnieje na to dowód „diagonalizacji”.$P \neq NP$

Ten wynik jest spowodowany przez Kozen. Nie wszyscy zgadzają się z tym, co nazywa dowodem „przekątnej”.

W Barriers I zespół czołowych teoretyków złożoności zgodził się, że Twierdzenie Barringtona było wynikiem, który najbardziej ich zaskoczył. Fortnow wyjaśnia Twierdzenie Barringtona tutaj: http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html

$NL$

Powiedziałbym, że ostatnie dzieło Jaina, Upadhyaya i Watrousa pokazujące, że QIP = IP = PSPACE jest dość zaskakujące. Moim zdaniem nie jest tak interesujące, że QIP = IP jest interesujące, ale fakt, że cały QIP może być symulowany w 3-okrągłym kwantowym dowodzie interaktywnym. Dość chłodna demonstracja mocy równoległości kwantowej.

Coś, co wciąż mnie zaskakuje, to fakt, że BPP to prawdopodobnie P - rodzi wiele filozoficznych pytań dotyczących natury losowości.

Twierdzenia Gödela o niekompletności

Twierdzenie o naturalnych dowodach Razborowa-Rudicha.

(AFAIK) Ludzie mieli wielką nadzieję na udowodnienie dolnych granic obwodu, ale po tym twierdzeniu wielu przestało działać i przeniosło się na inne tematy.

Licząca wersja problemu Monotone-SAT jest # P-kompletna.

$F$$F$

Byłem bardzo zaskoczony tym wynikiem, ponieważ wersja decyzyjna problemu Monotone-SAT jest banalna.

Powszechnie wiadomo, że istnieją problemy decyzyjne w P, których liczenie wersji jest # P-kompletne (jednym przykładem jest 2-SAT). Jednak moim zdaniem ten przypadek jest nieco „inny”: znalezienie satysfakcjonującego przypisania instancji Monotone-SAT jest nie tylko łatwe (jak na przykład znalezienie satysfakcjonującego przypisania instancji 2-SAT), jest dramatycznie trywialne. Nie tylko łatwe: trywialne, dosłownie. Zauważ, że biorąc pod uwagę, powiedzmy, instancję 2-SAT, może to być albo satysfakcjonująca, albo oczywiście niezadowalająca; chociaż biorąc pod uwagę instancję Monotone-SAT, wiesz z góry, że jest ona z pewnością satysfakcjonująca: nie może być niezadowalająca, w żadnym wypadku: potwierdza to, że nawet oba problemy są łatwe, ich poziomy „łatwości podejmowania decyzji” są różne. Z drugiej strony ich poziom „niepokoju” jest dokładnie taki sam.

Ten silny kontrast między następującymi faktami

1. Wybór Monotone-SAT jest głupiutki
2. Liczenie Monotone-SAT jest niezwykle trudne

jest co najmniej fascynujące dla IMHO.

Że aksjomaty wyboru i determinacji nie są kompatybilne.