Abstract of Paper

Problems which cannot be reduced to any proper subproblems
by Klaus Ambos-Spies

Abstract:

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.