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.
Asked
Active
Viewed 2,278 times
14
Kaveh
- 21,577
- 8
- 82
- 183
-
1this should be CW – Suresh Venkat Aug 31 '10 at 19:33
-
1I 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. – Shane Aug 31 '10 at 19:35
-
we should use this as an example for the FAQ – Suresh Venkat Aug 31 '10 at 23:07
1 Answers
11
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!).
Joshua Grochow
- 37,260
- 4
- 129
- 228