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.

cc.complexity-theory lo.logic computability big-list structural-complexity 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

Odpowiedzi:

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