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 proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP is contained
in subexponential time. 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 is contained in subexponential time. In fact, NP-simple sets cannot be complete for NP under bounded truth-table reductions under the stronger assumption that the intersection of UP and coUP is contained in subexponential time (while there is an oracle relative to which there is an NP-simple set conjunctively complete for NP).

We present several other results for different types of reductions, and show how to prove a similar result for NEXP which does not require any assumptions. We also prove that all NEXP-complete sets are P-levelable, extending work by Tran.

Most of the results are derived by the use of inseparable sets. This technique turns out to be very powerful in the study of truth-table and even (honest) Turing reductions.