Quels sont les articles classiques du domaine théorique récursif de la théorie de la complexité?

Deux documents que j'inclus sont:

D. Kozen, "Indexation des classes subrécursives" , STOC, 1978.
R. Ladner, «Sur la structure de la réductibilité du temps polynomial» , JACM, 1975.

cc.complexity-theory lo.logic computability big-list structural-complexity Kaveh
la source

cela devrait être CW

Suresh Venkat

Je suis d'accord avec Suresh. Juste pour ajouter: cette question pourrait probablement être reformulée de telle sorte qu'elle n'aurait pas besoin d'être un wiki communautaire (par exemple "Que dois-je lire en commençant par la théorie de la récursivité?"), De sorte qu'une seule réponse pourrait suffire. C'est actuellement trop ouvert.

Shane

nous devrions utiliser ceci comme exemple pour la FAQ

Suresh Venkat

Réponses:

Hajek, P. Hiérarchie arithmétique et complexité du calcul . Théorète. Comp. Sci. 8 (2): 227-237, 1979. A commencé l'étude de la complexité des ensembles d'indices (où leurs «complexités» se situent souvent quelque part dans la hiérarchie arithmétique; voir cette réponse à une autre question .)

Concernant l'étude des degrés polynomiaux (buzzword = "théorie des degrés polynomiaux", pour des recherches futures), je dirais que ces articles sont intéressants (plusieurs d'entre eux sont basés sur la technique de Ladner):

Homer, S. Degrés minimaux pour les réductibilités polynomiales . J. ACM 34 (2): 480-491, 1987.
Schöning, U. Minimal paires pour P . Théorète. Comp. Sci. 31: 41-48, 1984.
Downey, R. Nondiamond théorèmes pour la réductibilité du temps polynomial . Journal of Computer and System Sciences 45 (3): 385-195, 1992.
Downey, R. et Fortnow, L. Langues uniformément dures . Théorète. Comp. Sci. 298 (2): 303-315, 2003.
Fenner, S., Homer, S., Prium, R. et Schaefer, M. Hiérarchies hyperpolynomiales et saut polynomial . Théorète. Comp. Sci. 262: 241-256, 2001.

Une recherche de références avant et arrière trouvera probablement plusieurs autres articles dans la même zone (bien que ce ne soit pas une zone aussi grande!).

Joshua Grochow
la source