On sets Turing reducible to p-selective sets

Abstract

We consider sets Turing reducible to p-selective sets under various resource bounds and restricted number of queries to the oracle. We show that there is a hierarchy among the sets polynomial-time Turing reducible to p-selective sets with respect to the degree of a polynomial bounding the number of adaptive queries used by a reduction. We give a characterization of EXP / poly in terms of exponential-time Turing reducibility to p-selective sets. Finally we show that EXP can not be reduced to the p-selective sets under 2 lin time reductions with at most n k queries for any fixed k element of N.