Piękne wyniki w TCS

Niedawno mój przyjaciel (pracujący w TCS) wspomniał w rozmowie, że „chciał zobaczyć / poznać wszystkie (lub jak najwięcej) pięknych wyników w TCS w swoim życiu”. Ten rodzaj sprawił, że zastanawiałem się nad pięknymi wynikami w tej dziedzinie, a tym samym motywacją do następującego pytania:

Które wyniki (lub pomysły) są Twoim zdaniem piękne w informatyce teoretycznej? Byłoby wspaniale, gdybyś również podał powód. [Byłoby również w porządku, nawet jeśli pomysły pochodzą z matematyki, ale wzbudziły zainteresowanie i znalazły zastosowanie w TCS]

Zacznę od odpowiedzi jako przekątnego argumentu Cantora, ponieważ jest to prosty, elegancki, a jednocześnie potężny wynik.

Nierozstrzygalność problemu zatrzymania.

Piękna z wielu powodów. To wynik niemożliwości. Dowód wykorzystuje diagonalizację. Oświadczenie dotyczy szerokiej gamy modeli obliczeniowych. Można go formułować na różne sposoby, w szczególności przy użyciu standardowych języków programowania. Był to przełomowy wynik w historii komputerów. Rozszerzenie tego stwierdzenia prowadzi do twierdzenia Rice'a, stopni Turinga i wielu innych fajnych wyników. Itd Itd Itd Itd

Moim zdaniem korespondencja Curry-Howarda jest jednym z najpiękniejszych wyników teoretycznych i tym, co skłoniło mnie do badań.

Idea, że ​​dwa systemy, programy z jednej strony i dowody z drugiej strony mają dokładnie taką samą strukturę, ma niemal filozoficzny charakter: czy istnieją jakieś ogólne „wzorce rozumowania”?

Możliwość kryptografii z kluczem publicznym, na przykład schemat wymiany kluczy Diffie-Hellmana.

Przełamuje to bardzo silne przekonanie, że ludzie muszą się spotkać przed wymianą tajemnic na niepewnym kanale.

Byłem i nadal jestem zaskoczony algorytmem Euclida. Dla mnie jest to świadectwo siły ludzkiego myślenia - że ludzie mogliby sobie wyobrazić taki algorytm tak wcześnie (około 300 rpne, jeśli ufam mojej pamięci).

Szybkie przewijanie do przodu, jest przytłaczająca literatura na ten temat. Myślę, że lista Scotta Aaronsona powinna być pomocna w tym względzie - jednak, jak sam Aaronson mówi, że nie jest kompletna (i nie do końca teoretyczna)

Technika Yao polegająca na zastosowaniu twierdzenia Minmaxa von Neumanna do udowodnienia dolnych granic dla algorytmów randomizowanych. Uważam to za coś nie z tego świata.

Probabilistyczna metoda udowodnienia istnienia obiektów, które trudno nam zbudować, w tym lemata lokalna Lovasz. Te techniki są tak proste, ale tak potężne.

Konstrukcje teorii kodowania Madhu Sudana z wykorzystaniem wielomianów.

Ekspandery (zaczęło się jako wykresy Ramanujana) oraz Ekstraktory i ich aplikacje w Pseudolosie.

Algorytm szybkiej transformacji Fouriera Cooleya i Tukeya w celu znalezienia DFT. (Chociaż, jak zakładał Tukey, było to ponowne odkrycie dobrze znanej techniki, przynajmniej znanej Gaussowi!)

Twierdzenie Barringtona (bardzo zaskakujący wynik w swoim czasie)

Twierdzenie o równoległych powtórzeniach (chociaż wynik jest dobry, dowód nie jest łatwy)

Funkcja Lovasz Theta do oszacowania pojemności shannona wykresu.

Algorytm elipsoidalny, który pokazał, że LP jest w P, zaskakuje wielu w tym samym czasie, gdy wielu nadal podejrzewa, że ​​może być NP-Complete.

zaskakująco jedna z najbardziej oczywistych odpowiedzi nie została jeszcze dodana. czasami ktoś zbyt wiele pracuje z czymś, aby widzieć to bezstronnie. Teoria NP kompletności zainicjowanej przez Cooka / Levin i natychmiast powielanego przez Karp, który dał wczesne wskazanie jego ubiquitousness, jeszcze bardziej przewidujący z perspektywy czasu. pod wieloma względami jest to narodziny nowoczesnej teorii TCS i teorii złożoności, a jej podstawowe / kluczowe / notoryczne pytanie P =? NP jest nadal otwarte po czterech dekadach intensywnych badań / ataku. P =? NP ma nagrodę Claymath w wysokości 1 mln USD za swoje rozwiązanie.

Dowód Cooka wprowadził NDTM, który najwyraźniej wcale nie jest jedynie teoretyczną ciekawością, ale prawie niezwykle podstawową częścią TCS. wypuścił tysiąc statków, że tak powiem. co więcej, nieustannie opiera się / przeciwstawia wysiłkom poprzez jedną z innych kluczowych / potężnych technik TCS wymienionych na tej liście, przekątną, widzianą np. w wynikach BGS-75 Oracle / Relatywizacja - co sugeruje, że musi być coś egzotycznego i innego w każdej możliwej rozwiązanie, również dalej zasugerowane / rozwinięte w dokumencie Razborov-Rudich Natural Proofs (nagroda Godela 2007).

istnieje wiele, wiele referencji na temat, ale jedno z ostatnich relacji z pierwszej ręki historii można znaleźć w The P =? NP Question i Godel's Lost Letter autorstwa RJ Liptona

Złożoność Kołmogorowa i metoda nieściśliwości .

Metoda nieściśliwości - oparta na złożoności Kołmogorowa - zapewniła nowy i intuicyjny sposób formułowania dowodów. W typowym dowodzie wykorzystującym metodę nieściśliwości, najpierw wybiera się obiekt nieściśliwy z omawianej klasy. Argument niezmiennie mówi, że jeśli żądana właściwość nie jest zachowana, to w przeciwieństwie do założenia obiekt można skompresować, co stwarza wymaganą sprzeczność.

Zobacz na przykład dowód, że istnieje nieskończona liczba liczb pierwszych, alternatywny dowód twierdzenia o niekompletności Godela lub związki między złożonością Kołmogorowa a złożonością obliczeniową ...

Byłem (i wciąż jestem) zdumiony twierdzeniem Kleene'a o drugiej rekurencji . Na pierwszy rzut oka wydaje się prosty i mało przydatny, ale później odkryłem, że jest głęboki zarówno matematycznie, jak i filozoficznie.

Kiedy przeczytałem również o wariancie sprawdzonym na maszynach Turinga (bardzo nieformalnie stwierdzając, że maszyny mogą uzyskać własne opisy lub równoważnie, że istnieją maszyny, które generują własny opis, jak program, który drukuje się sam ...), poczułem, że mój mózg się wykręca. tak trudne, ale zaintrygowane jak nigdy przedtem. Następnie zobaczysz, w jaki sposób twierdzenie to daje jeden wiersz dowodu na nierozstrzygalność problemu zatrzymania i nierozpoznawalności maszyn minimalnych ... itd.

Twierdzenia Shannona o kodzie źródłowym i kanałowym.

Definicja matematyczna, która odróżniała przekaz, odbiornik od medium i która ignorowała semantykę wiadomości, była dużym krokiem. Entropia w kontekście danych jest fantastycznie użytecznym pojęciem. A ponieważ teoria informacji powinna być lepiej znana.

Piękny wynik, który opiera się na twierdzeniu PCP, stwierdza, że ​​trudne jest obliczenie (NP-trudne), aby spełnić więcej niż 7/8 klauzul wzoru 3SAT, nawet w przypadku warunków zadowalających.

algorytm Shors dla faktoringu w BQP . moim zdaniem / pamięć, obliczenia kwantowe były bardziej ciekawostką teoretyczną, aż do tego wyniku w 1994 r., kiedy to wydawało się, że eksplozja literatury i badań w dziedzinie obliczeń QM. jest to prawdopodobnie jeden z najważniejszych znanych algorytmów QM. przyznał nagrodę Gödel w 1999 roku. ujawnia również, że faktoring w obliczeniach QM jest w pewnym sensie nieco lepiej rozumiany niż w obliczeniach klasycznych, gdzie np. wciąż pozostaje otwarte pytanie, czy faktoring jest kompletny.

Wydaje mi się, że test pierwotności czasu AKS P jest dość piękny pod wieloma względami. przełom w tym czasie, jeden z wielkich, ale raczej rzadkich przełomów w teorii złożoności w naszych czasach. rozwiązuje problem sięgający starożytności greckiej i odnosi się do niektórych z najwcześniejszych wynalezionych algorytmów (sito eratostenów), tj. efektywnego identyfikowania liczb pierwszych. jest to konstruktywny dowód na to, że wykrywanie pierwotności ma wartość P, w przeciwieństwie do wielu wielkich dowodów, które niestety nie są konstruktywne.

jest połączony z algorytmem kryptograficznym RSA wspomnianym w innej odpowiedzi, ponieważ algorytm ten musi szybko znaleźć duże liczby pierwsze, przed algorytmem AKS było to możliwe tylko probabilistycznie. jest zasadniczo związane z teorią liczb i innymi głębokimi problemami, np. hipotezą Riemanna, która pod wieloma względami jest oryginalną dziedziną algorytmiki.

przyznał nagrodę Gödel 2006 i nagrodę Fulkerson 2006

Myślę, że małe twierdzenie grafów autorstwa Robertsona i Seymour'a było najwspanialszymi teoriami, jakie kiedykolwiek widziałem (i częściowo je przeczytałem). Przede wszystkim jest to cicho skomplikowane, ale podstawowe przypuszczenia nie są trudne i być może każdy, kto pracuje w TCS, może je odgadnąć. Ich niezwykły wysiłek, aby je udowodnić, był wspaniały. W rzeczywistości po przeczytaniu niektórych artykułów z tej serii rozumiem siłę ludzkiego umysłu.

Również małe twierdzenie o grafach ma duży wpływ na różne pola TCS. Podobnie jak teoria grafów, algorytm aproksymacyjny, algorytmy parametryzowane, logika, ...

Jedną z moich ulubionych rodzin wyników jest rozstrzyganie różnych problemów z pozornie nieskończonej natury.

1. Teoria pierwszego rzędu rzeczywistych pól zamkniętych jest rozstrzygalna (według Tarskiego). Geometria euklidesowa jest także modelem aksjomatów rzeczywistych zamkniętych pól, stąd też według Tarskiego rozstrzygające są zdania pierwszego rzędu w tym modelu.
2. Arytmetyka Presburgera jest rozstrzygalna.
3. Teoria pierwszego rzędu algebraicznie zamkniętych pól (w tym liczb zespolonych) jest rozstrzygalna.
4. Monadyczna logika drugiego rzędu nad nieskończonymi (i skończonymi) słowami jest rozstrzygalna. Dowód jest elegancki i można go nauczyć studentów.

Istnieje wiele cudownych wyników na temat algorytmów probabilistycznych, które są zwodniczo proste i stanowią duży krok naprzód w naszym podejściu do obliczeń.

Trik von Neumanna dotyczący wprowadzenia uczciwej monety za pomocą stronniczości. Jesteśmy teraz tak przyzwyczajeni do algorytmów probabilistycznych, ale z zewnętrznej perspektywy jest to niewiarygodnie fajne. Zarówno algorytm, jak i dowód są dostępne dla każdego, kto zna prawdopodobieństwo w szkole średniej.

Wynik Tima Griffina, który kontroluje takich operatorów, jak call/cclogika klasyczna, rozszerza korespondencję Curry-Howarda.

Zasadniczo wpisywanie call/ccjest takie, że jeśli ma typ , to ma typ . Działa to przy interpretacji typu jako , co jest standardem w logice i odpowiada typowi funkcji, która przyjmuje i nigdy nie zwraca. To właśnie robi kontynuacja, dzięki czemu korespondencja działa.¬ ¬ τ c a l l / c c ( E ) τ ¬ τ τ → ⊥ $E$$\neg\neg \tau$$\mathtt{call/cc}{(E)}$$\tau$$\neg\tau$$\tau\rightarrow\bot$$\tau$

Jego praca zatytułowana „Formuła jako pojęcie kontroli” pojawia się w POPL 1990.

Moim ulubionym jest liniowy algorytm czasu Rabina do obliczania najbliższej pary punktów na płaszczyźnie (a ściślej jej uproszczenie). Omawia znaczenie modelu obliczeniowego, moc algorytmów losowych i elegancki sposób myślenia o algorytmach losowych.

To powiedziawszy, CS wciąż jest daleki od osiągnięcia poziomu elegancji, jaki napotyka się w matematyce (no cóż, mieli 5000 lat przewagi), od podstawowych definicji / wyników w rachunku różniczkowym, topologicznym (twierdzenia o stałym punkcie), kombinatoryki, geometrii (twierdzenie Pitagorasa http : //en.wikipedia.org/wiki/Plik: Pythag_anim.gif ) itp.

Jeśli szukasz piękna, szukaj go wszędzie ...

Ten wynik jest prawdopodobnie nieco nowy, aby można go było uznać za fundamentalny, ale uważam, że interpretacja typów jako homotopii kwalifikuje się. Ten widok pozwala interpretować typy z konstruktywnej teorii typów jako zestawy o określonych właściwościach geometrycznych, w tym przypadku homotopii .

Uważam ten punkt widzenia za szczególnie piękny, ponieważ upraszcza on niektóre wcześniej złożone obserwacje dotyczące teorii typów, na przykład fakt, że „aksjomat K” nie jest możliwy do wyprowadzenia .

Przegląd tego obiecującego pola autorstwa Steve'a Awodeya można znaleźć tutaj .

Dowód braku wiedzy to bardzo interesująca koncepcja. Pozwala bytowi, dowodzącemu, udowodnić (z dużym prawdopodobieństwem) innemu bytowi, weryfikatorowi, że zna on „sekret” (rozwiązanie jakiegoś problemu NP, modułowy pierwiastek kwadratowy z pewnej liczby, dyskretny dziennik pewnej liczby itp.) bez podawania jakichkolwiek informacji na temat sekretu (co na pierwszy rzut oka jest trudne, ponieważ pierwszym pomysłem na udowodnienie, że znasz sekret, jest przekazanie tajemnicy i każda komunikacja, która mogłaby skutkować weryfikator wierzący, że znasz tajemnicę, może z góry tylko zwiększyć wiedzę weryfikatora na temat tajemnicy).