<p>Hajek, P. <a href="http://dx.doi.org/10.1016/0304-3975(79)90046-X" rel="nofollow noreferrer">Arithmetical hierarchy and complexity of computation</a>. 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 <a href="https://cstheory.stackexchange.com/questions/161/can-it-be-determined-if-language-l-lies-in-np/162#162">this answer</a> to <a href="https://cstheory.stackexchange.com/questions/161/can-it-be-determined-if-language-l-lies-in-np">another question</a>.)</p>

<p>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):</p>

<ul>
<li>Homer, S. <a href="http://doi.acm.org/10.1145/23005.23009" rel="nofollow noreferrer">Minimal degrees for polynomial reducibilities</a>.  J. ACM 34(2):480-491, 1987.</li>
<li>Schöning, U. <a href="http://dx.doi.org/10.1016/0304-3975(84)90124-5" rel="nofollow noreferrer">Minimal pairs for P</a>. Theoret. Comp. Sci. 31: 41-48, 1984.</li>
<li>Downey, R. <a href="http://dx.doi.org/10.1016/0022-0000(92)90032-E" rel="nofollow noreferrer">Nondiamond theorems for polynomial time reducibility</a>. Journal of Computer and System Sciences 45(3):385-195, 1992.</li>
<li>Downey, R. and Fortnow, L. <a href="http://dx.doi.org/10.1016/S0304-3975(02)00810-1" rel="nofollow noreferrer">Uniformly hard languages</a>. Theoret. Comp. Sci. 298(2): 303-315, 2003.</li>
<li>Fenner, S., Homer, S., Prium, R. and Schaefer, M. <a href="http://dx.doi.org/10.1016/S0304-3975(00)00193-6" rel="nofollow noreferrer">Hyper-polynomial hierarchies and the polynomial jump</a>. Theoret. Comp. Sci. 262: 241-256, 2001.</li>
</ul>

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

CC BY-SA 2.5
2010-09-01T02:01:45.340Z
2010-09-01T02:01:45.340Z
2017-04-13T12:32:28.053Z
Joshua Grochow
<p>Two papers I would include are:</p>

<ol>
<li><p>D. Kozen, <a href="http://doi.acm.org/10.1145/800133.804358" rel="nofollow">"Indexing of subrecursive classes"</a>, STOC, 1978.</p></li>
<li><p>R. Ladner, <a href="http://doi.acm.org/10.1145/321864.321877" rel="nofollow">"On the Structure of Polynomial Time Reducibility"</a>, JACM, 1975.</p></li>
</ol>

CC BY-SA 2.5
2010-08-31T19:33:19.123Z
this should be CW
Suresh Venkat
CC BY-SA 2.5
2010-08-31T19:35:40.197Z
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.
Shane
CC BY-SA 2.5
2010-08-31T23:07:25.463Z
we should use this as an example for the FAQ
Suresh Venkat
<cc.complexity-theory><lo.logic><computability><big-list><structural-complexity>
What are the classic papers from the recursion theoretic area of complexity theory?
Kaveh
# What are the classic papers from the recursion theoretic area of complexity theory?

(Asked by: username_0 on 2010-08-31)

Two papers I would include are:

1. D. Kozen, ["Indexing of subrecursive classes"](http://doi.acm.org/10.1145/800133.804358), STOC, 1978.
2. R. Ladner, ["On the Structure of Polynomial Time Reducibility"](http://doi.acm.org/10.1145/321864.321877), JACM, 1975.

**Tags:** cc.complexity-theory, lo.logic, computability, big-list, structural-complexity
> **Comments:**
> **username_1**: this should be CW  
> **username_2**: 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.  
> **username_1**: we should use this as an example for the FAQ  

---

## 1 answers

### Answer by username_3 on 2010-09-01. Score: 11 | Accepted answer

Hajek, P. [Arithmetical hierarchy and complexity of computation](http://dx.doi.org/10.1016/0304-3975(79)90046-X). 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](https://cstheory.stackexchange.com/questions/161/can-it-be-determined-if-language-l-lies-in-np/162#162) to [another question](https://cstheory.stackexchange.com/questions/161/can-it-be-determined-if-language-l-lies-in-np).)

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](http://doi.acm.org/10.1145/23005.23009). J. ACM 34(2):480-491, 1987.
* Schöning, U. [Minimal pairs for P](http://dx.doi.org/10.1016/0304-3975(84)90124-5). Theoret. Comp. Sci. 31: 41-48, 1984.
* Downey, R. [Nondiamond theorems for polynomial time reducibility](http://dx.doi.org/10.1016/0022-0000(92)90032-E). Journal of Computer and System Sciences 45(3):385-195, 1992.
* Downey, R. and Fortnow, L. [Uniformly hard languages](http://dx.doi.org/10.1016/S0304-3975(02)00810-1). Theoret. Comp. Sci. 298(2): 303-315, 2003.
* Fenner, S., Homer, S., Prium, R. and Schaefer, M. [Hyper-polynomial hierarchies and the polynomial jump](http://dx.doi.org/10.1016/S0304-3975(00)00193-6). 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!).


---

