Rozpocznij naukę złożoności dowodu

12

Niedawno zacząłem dużo czytać o złożoności dowodów i bardzo podobało mi się to, co czytałem. Naprawdę chciałbym dowiedzieć się więcej na ten temat, ale mam trudności ze znalezieniem dobrego materiału dla początkujących. Czy ktoś mógłby polecić jakieś podstawy?

cc.complexity-theory lo.logic proof-complexity

— Yugioh Mishima
źródło

Czy sprawdziłeś odniesienia w złożoności dowodu złożonego z artykułu z Wikipedii ? Książka Steve'a i Phuonga jest stosunkowo łatwa do odczytania.

— Kaveh

2

Podobała mi się prezentacja Olafa Beyersdorffa w Helsinkach tego lata. Sprawdź jego slajdy tutaj .

— Juho,

12

To zależy od tego, jaki poziom „początkujący” chcesz mieć. Nie sądzę, aby istniał naprawdę dobry tekst na poziomie licencjackim o złożoności dowodu (prawdopodobnie dotyczy to większości wyspecjalizowanych podobszarów o złożoności). Ale w przypadku źródeł dla początkujących (absolwentów) zaleciłbym coś w rodzaju dobrego zrozumienia podstawowej wielkości wykładniczej dolnej granicy odrzucenia rozdzielczości zasady szuflady (poprzez losowe ograniczenia, kompromis szerokości i wykonalną interpolację), i aby rozwinąć z tego wskaż dalej. Można to osiągnąć (w przybliżeniu) w następujący sposób:

Stasys Jukna, Extremal Combinatorics with Applications in Computer Science, 2001, Springer-Verlag, sekcja 4.8.
Eli Ben-sasson i Avi Wigderson, Short Proofs are Narrow - Resolution made Simple (2000), JACM.
P. Beame i T. Pitassi, Złożoność dowodu propozycyjnego: przeszłość, teraźniejszość i przyszłość, aktualne trendy w informatyce teoretycznej: wkraczanie w XXI wiek (red. G. Paul, G. Rozenberg i A. Salomaa), World Scientific Publishing , 2001, s. 42--70.
Pavel Pudlák, Dolne granice rozdzielczości i wycinania płaszczyzn proofów i obliczeń monotonicznych, The Journal of Symbolic Logic, t. 62 (1997), no. 3, s. 981–998.

Możesz także zapoznać się z bardziej samodzielnym i długim tekstem:

Peter Clote i Evangelos Kranakis, funkcje boolowskie i modele obliczeniowe (rozdział 5)

Dla bardziej logicznej strony złożoności dowodu, jak sugerował Kaveh, możesz zacząć czytać pierwsze rozdziały:

Stephen Cook i Phuong Nguyen, Logiczne podstawy dowodu złożoności (Perspectives in Logic, Cambridge Press, 2010).

— Iddo Tzameret
źródło

1

Dziękuję Ci bardzo! Wykopię je i zobaczę, jak się okażą

— Yugioh Mishima,

6

Dla bardziej algebraicznej strony złożoności dowodu zalecam rozpoczęcie od ankiety Pitassi z 1996 r .:

T. Pitassi. Algebraiczne systemy dowodzenia twierdzeń , w serii DIMACS z dyskretnej matematyki i informatyki teoretycznej, tom 31, Deskryptywna złożoność i modele skończone, Immerman i Kolaitis (red.), S. 215–244, 1996.

W celu szybkiego przeglądu można również zapoznać się z rozdziałem 5 książki Clote - Kranakis wspomnianej już przez Iddo, która zawiera sekcję dotyczącą algebraicznych systemów dowodowych.

Pierwszą pracą badawczą, którą polecam przeczytać (zarówno dlatego, że jest przełomowa, jak i przyjemna), jest praca, w której wprowadzono system dowodzenia Groebnera lub rachunku wielomianowego:

Clegg, Matthew; Edmonds, Jeffery; Impagliazzo, Russell. Wykorzystanie algorytmu bazowego Groebnera do znalezienia dowodów niezadowolenia STOC 1996, 174-183. (Dostępne również na stronach autora bez paywall).

— Joshua Grochow
źródło

6

Uważam, że te wstępne notatki z wykładów są łatwe do odczytania: Wykłady IAS Paula Beame'a

— Dai Le
źródło

2

Notatki z wykładów IAS Paula Beame'a są bardzo ładne i dają dobry przegląd tego obszaru. Należy jednak pamiętać, że istnieją pewne problemy z niektórymi stwierdzeniami typu „jeśli świnie potrafią latać”. Próbowałem podać poprawione wersje w (mini-ankiecie w) rozdziale 4 mojej pracy doktorskiej: Jakob Nordström. Krótkie dowody mogą być przestrzenne: zrozumienie przestrzeni w rozdzielczości. Praca doktorska, Royal Institute of Technology, Sztokholm, Szwecja, maj 2008 r. ( Www.csc.kth.se/~jakobn/research/PhDthesis.pdf ).

— Jakob Nordstrom

5

Najnowsza i najbardziej aktualna ankieta złożoności dowodu ogólnego zastosowania prawdopodobnie pochodzi od Nathana Segerlinda:

Nathan Segerlind: Złożoność dowodów dowodowych. Biuletyn Symbolic Logic 13 (4): 417-481, 2007 ( http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps ).

A teraz ostrzeżenia dla dwóch bezwstydnych wtyczek…

Jeszcze bardziej aktualna ankieta, ale ściślej skoncentrowana na pytaniach dotyczących rozmiaru dowodu, przestrzeni dowodu i kompromisów między wielkością, to:

Jakob Nordström. Gry Pebble, złożoność dowodu i kompromisy czasoprzestrzenne. Logical Methods in Computer Science, tom 9, wydanie 3, artykuł 15, wrzesień 2013 ( http://www.lmcs-online.org/ojs/viewarticle.php?id=674 ).

Istnieją również notatki z wykładu z nieco niedawnego kursu, który podałem na temat „dolnego spektrum” złożoności dowodu (tj. Stosunkowo słabych systemów dowodu, takich jak rozdzielczość, rachunek wielomianowy i płaszczyzny cięcia) i połączeń do rozwiązywania SAT. Te uwagi można znaleźć na stronie http://www.csc.kth.se/~jakobn/teaching/proofcplx11/#scribe-notes (niektóre są nadal w toku, ale te, które są dostępne, powinny być w dobrej formie).

— Jakob Nordstrom
źródło