Jakie są klasyczne artykuły z teoretycznego obszaru teorii złożoności rekurencyjnej?

Dwa dokumenty, które chciałbym załączyć to:

D. Kozen, „Indeksowanie klas subrekursywnych” , STOC, 1978.
R. Ladner, „O strukturze wielomianowej redukcji czasu” , JACM, 1975.

— Kaveh
źródło

powinien to być CW

— Suresh Venkat

Zgadzam się z Suresh. Wystarczy dodać: to pytanie można prawdopodobnie przeformułować w taki sposób, aby nie musiało to być wiki społeczności (np. „Co powinienem przeczytać, rozpoczynając od teorii rekurencji?”), Tak aby wystarczyła jedna odpowiedź. Obecnie jest zbyt otwarty.

— Shane

powinniśmy to wykorzystać jako przykład dla FAQ

— Suresh Venkat

Hajek, P. Hierarchia arytmetyczna i złożoność obliczeń . Teoretyczna Komp. Sci. 8 (2): 227-237, 1979. Rozpoczął badanie złożoności zbiorów indeksów (gdzie ich „złożoność” często leży gdzieś w hierarchii arytmetycznej; patrz odpowiedź na inne pytanie ).

Na temat badań stopni wielomianowych (modne hasło = „teoria stopni wielomianowych”, ze względu na przyszłe wyszukiwania) powiedziałbym, że te artykuły są interesujące (niektóre z nich oparte są na technice Ladnera):

Homer, S. Minimalne stopnie redukcji wielomianów . J. ACM 34 (2): 480-491, 1987.
SCHöNING U. par minimalnych dla P . Teoretyczna Komp. Sci. 31: 41–48, 1984.
Twierdzenia Downeya R. Nondiamonda o wielomianowej redukcji czasu . Journal of Computer and System Sciences 45 (3): 385–195, 1992.
Downey, R. i Fortnow, L. Jednolicie twarde języki . Teoretyczna Komp. Sci. 298 (2): 303–315, 2003.
Fenner, S., Homer, S., Prium, R. i Schaefer, M. Hierarchie hiper-wielomianowe i skok wielomianowy . Teoretyczna Komp. Sci. 262: 241–256, 2001.

Prawdopodobnie wyszukiwanie referencji do przodu i do tyłu pozwoli znaleźć kilka innych artykułów w tym samym obszarze (choć nie jest to tak duży obszar!).

— Joshua Grochow
źródło