Dokumentuje każdy teoretyk złożoności, który powinien przeczytać

14

Rozpoczynam doktorat tej jesieni i planuję pracować nad teorią złożoności.

Tworzę listę ważnych prac, które powinien znać każdy teoretyk złożoności.

Jakie dokumenty poleciłbyś osobie takiej jak ja? I proszę krótko wyjaśnić, dlaczego uważasz, że ten papier jest ważny.

cc.complexity-theory reference-request big-list nowy student
źródło
8
Czy już sprawdziłeś Jakie artykuły każdy powinien przeczytać?
Juho,
3
Tak. Dlaczego nie jest to tylko kopia tego pytania.
Suresh Venkat,
2
OP prawdopodobnie nie zauważył tego pytania.
Huck Bennett,
3
Nie sądzę, że jest to duplikat drugiego pytania. Drugie pytanie dotyczy artykułów, które każdy powinien przeczytać (tj. Interesujących wszystkich teoretycznych informatyków), ten wydaje się być studentem rozpoczynającym badania w teorii złożoności, który szuka ważnych artykułów w teorii złożoności. Takie prace mogą nie być interesujące dla teoretycznych informatyków, którzy nie są ekspertami w teorii złożoności. Odpowiedzi będą różne, więc nie będą duplikatami IMO.
Kaveh
2
@Kaveh: Myślę, że to pytanie jest przejmowane przez inne. Wiele z ich odpowiedzi dotyczy dokumentów o złożoności.
Huck Bennett,

Odpowiedzi:

10

Niejednolity obwód ACC Ryana Williama i wszystkie cytowane w nim wyniki.

To nie tylko ostatni ważny wynik, to bardzo dobrze napisany artykuł. Ponadto wyniki, których używa i cytuje, obejmują całkiem niezły zakres wyników złożoności nasienia. Więc jeśli przejrzysz referencje i je przeczytasz - dojdziesz do punktu, w którym rozumiesz każdą część ACC niższej granicy od pierwszych zasad - pomyślałbym, że byłby to doskonały początek edukacji złożoności dla absolwentów.

Joshua Grochow
źródło
3
zdecydowanie zaleca się również swobodną wycieczkę: arxiv.org/abs/1111.1261
Sasho Nikolov
9

Chociaż nie jest to bezpośrednia odpowiedź na twoje pytanie, chciałbym polecić następującą książkę:

Klejnoty teoretycznej informatyki Uwe Schöninga i Randalla J. Pruima.

Większość jego rozdziałów dotyczy teorii złożoności. Książka może być postrzegana jako niezły zbiór wyników niektórych ważnych prac naukowych. Możesz pobrać dokumenty z wyników!

Abuzer Yakaryilmaz
źródło
7

Polecam wyniki w

Towarzysz teorii teorii złożoności Hemaspaandra i Ogihara.

Jest on zorganizowany wokół technik, a nie wyników, choć często technika została opracowana dla określonego wyniku i obejmuje kilka przełomowych wyników i ważnych technik dowodowych.

Joshua Grochow
źródło
6

1) R. Lader, N. Lynch i A. Selman. Porównanie wielomianowych redukcji czasu. Theoretical Computer Science, 1 (2): 103-124, 1975. 6) E. Allender. Złożoność zbiorów rzadkich w P. W materiałach z konferencji 1. Struktura teorii złożoności, strony 1-11. Springer-Verlag Wykładowe notatki z informatyki # 223, czerwiec 1986. 6) R. Beigel. O relatywnej sile dodatkowych ścieżek akceptacji. W obradach IV Konferencji Teoria Złożoności, strony 216–224. IEEE Computer Society Press, czerwiec 1989 r. 9) R. Beigel, H. Buhrman i L. Fortnow. NP może nie być tak łatwe jak wykrywanie unikalnych rozwiązań. W materiałach z 30. sympozjum ACM na temat teorii obliczeń, strony 203–208. ACM Press, maj 1998 r.

2) LG Valiant „Złożoność obliczania trwałego”, Theoretical Computer Science, 8 (1979), s. 181-201.

3) A. Blass i Y. Gurevich „O wyjątkowym problemie satysfakcji”. Informacja i kontrola, 55 (1-3) strony 80-88, 1982.

4) J. Balcazar, R. Book & U. Schoning. „The Hierarchy-Time & Sparse Oracles” w czasopiśmie wielomianowym ”Journal of Associate for Computing Machinery, tom 33, nr 3. Lipiec 1986 r. strony 603–617.

5) LG Valiant i V. Vazirani „NP jest tak łatwe, jak wykrywanie unikalnych rozwiązań” Theoretical Computer Science 47 (1986) strony 85-93.





7) R.Beigel & J. Gill „Liczenie klas: progi, parzystość, mody i skromność” Teoretyczna informatyka Tom 103 Strony 3-23. 1992.

8) S. Fenner, L. Fortnow i S. Kurtz „Gap-Defable Counting Classes” Journale of Computer And System Sciences Tom 48 Strony 116-148 1994.



10) B. Borchert, L. Hemaspaandra i J. Rothe „Restrictive Acceptance Suffices for Equivalance Problems” LMS J Comput. Matematyka 3 strony 86-95 2000.

Tayfun Pay
źródło
5

Zgadzam się z powyższą odpowiedzią Abuzera: Myślę, że każdy rozdział książki o złożoności obliczeniowej (jak „ Złożoność obliczeniowa Arory i Baracka : współczesne podejście ” lub „ Złożoność obliczeniowa: perspektywa koncepcyjna ” Goldreicha ) zawiera (i często wyjaśnia w bardziej przejrzysty sposób sposób) wyniki pochodzące z ważnych / podstawowych artykułów. Podczas czytania książki o złożoności obliczeniowej możesz lepiej zrozumieć, dlaczego są one uważane za ważne.

Są to jednak moje ulubione:

Marzio De Biasi
źródło