14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ this should be CW $\endgroup$ – Suresh Venkat Aug 31 '10 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 '10 at 19:35
  • $\begingroup$ we should use this as an example for the FAQ $\endgroup$ – Suresh Venkat Aug 31 '10 at 23:07
11
$\begingroup$

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!).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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