Two papers I would include are:

  1. D. Kozen, "Indexing of subrecursive classes", STOC, 1978.

  2. R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.

  • 1
    $\begingroup$ this should be CW $\endgroup$ Aug 31, 2010 at 19:33
  • 1
    $\begingroup$ I agree with Suresh. Just to add: this question could probably be rephrased in such a way that it wouldn't need to be community wiki (e.g. "What should I read when starting with recursion theory?"), such that a single answer could suffice. It's currently too open-ended. $\endgroup$
    – Shane
    Aug 31, 2010 at 19:35
  • $\begingroup$ we should use this as an example for the FAQ $\endgroup$ Aug 31, 2010 at 23:07

1 Answer 1


Hajek, P. Arithmetical hierarchy and complexity of computation. Theoret. Comp. Sci. 8 (2): 227-237, 1979. Started the study of the complexities of index sets (where their "complexities" often lie somewhere in the arithmetical hierarchy; see this answer to another question.)

On the study of polynomial-time degrees (buzzword="polynomial-time degree theory", for the sake of future searches) I'd say these papers are of interest (several of them are based on Ladner's technique):

Probably a forward and backwards reference search will find several more papers in the same area (though it's not that big an area!).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.