Two papers I would include are:
D. Kozen, "Indexing of subrecursive classes", STOC, 1978.
R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ this should be CW $\endgroup$– Suresh VenkatAug 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$– ShaneAug 31, 2010 at 19:35
-
$\begingroup$ we should use this as an example for the FAQ $\endgroup$– Suresh VenkatAug 31, 2010 at 23:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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):
- Homer, S. Minimal degrees for polynomial reducibilities. J. ACM 34(2):480-491, 1987.
- Schöning, U. Minimal pairs for P. Theoret. Comp. Sci. 31: 41-48, 1984.
- Downey, R. Nondiamond theorems for polynomial time reducibility. Journal of Computer and System Sciences 45(3):385-195, 1992.
- Downey, R. and Fortnow, L. Uniformly hard languages. Theoret. Comp. Sci. 298(2): 303-315, 2003.
- Fenner, S., Homer, S., Prium, R. and Schaefer, M. Hyper-polynomial hierarchies and the polynomial jump. Theoret. Comp. Sci. 262: 241-256, 2001.
Probably a forward and backwards reference search will find several more papers in the same area (though it's not that big an area!).