|Abstract of Paper|
Problems which cannot be reduced to any proper subproblems
by Klaus Ambos-Spies
For any reducibility $\le_r$ , an infinite set A is called introimmune under $r$-reducibility (or shortly $\le_r$-introimmune) if any subset B of A to which A can be $r$-reduced is a finite variant of A. Soare (1969) has shown that there is a $\le_T$-introimmune set but, as Simpson (1978) has shown, such a set has to be extremely complex, namely Turing hard for the class of hyperarithmetical sets. In particular no set definable in first order arithmetic can be $\le_T$-introimmune. Cintioli and Silvestri (2003) started the investigation of introimmunity under strong and subrecursive reducibilities. They have shown that for some strong reducibilities, namely for (nondeterministic) many-one reducibility and for conjunctive reducibility there are arithmetical (but necessarily nonrecursive) sets which are introimmune under these reducibilities. They raised the question whether there are recursive (or at least recursively enumerable) sets which are introimmune under some of the common subrecursive reducibilities. In particular they have asked whether there is a recursive set which is introimmune under polynomial-time bounded Turing reducibility (p-T-reducibility for short). Here we answer this question affirmatively. We show that there is a recursive - in fact exponential-time computable - set A which is p-T-introimmune. Furthermore, straightforward modifications of our construction yield recursive sets which are introimmune under any given standard subrecursive reducibility and recursively approximable sets which are introimmune under truth-table reducibility.