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
źródło
Odpowiedzi:
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:
Dla bardziej logicznej strony złożoności dowodu, jak sugerował Kaveh, możesz zacząć czytać pierwsze rozdziały:
źródło
Dla bardziej algebraicznej strony złożoności dowodu zalecam rozpoczęcie od ankiety Pitassi z 1996 r .:
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:
źródło
Uważam, że te wstępne notatki z wykładów są łatwe do odczytania: Wykłady IAS Paula Beame'a
źródło
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).
źródło