Simplicity and Strong Reductions
Marcus Schaefer, Stephen Fenner · 1997
A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha [HLY86] proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless NP # coNP # SUBEXP. However, we can exhibit a relativized world in which there is an NP-simple set that is complete under Turing (Cook) reductions, even conjunctive reductions. This raises the questions whether the result by Hartmanis, Li and Yesha generalizes to reductions of intermediate strength. We show that NP-simple sets are not complete for NP under positive bounded truth-table reductions unless UP # SUBEXP. In fact, NP-simple sets cannot be complete for NP under bounded truth-table reductions under the stronger assumption that UP # coUP ## SUBEXP (while there is an oracle relative to which there is an NP-simple set conjuntively complete for NP). We present several other results for di#erent types of reductions, a...