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,

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:

Twierdzenie Savitcha: Savitch, Walter J. (1970), „Relacje między niedeterministycznymi i deterministycznymi złożonościami taśm”, Journal of Computer and System Sciences 4 (2): 177–192, DOI: 10.1016 / S0022-0000 (70) 80006-X
Twierdzenie Cooka-Levina : Cook, Stephen (1971). „ Złożoność procedur dowodzenia twierdzeń ”. Materiały z trzeciego dorocznego sympozjum ACM na temat teorii obliczeń. s. 151–158
J. Hopcroft, W. Paul i L. Valiant, On time vs. Space , J. ACM, 24, 332–337 (1977)
TP Baker, J. Gill, R. Solovay. Relatywizacje P =? Pytanie NP. SIAM Journal on Computing, 4 (4): 431-442 (1975)

— Marzio De Biasi
źródło