On sets turing reducible to p-selective sets

Research paper by H. J. Burtschick, W. Lindner

Indexed on: 30 Jul '07Published on: 30 Jul '07Published in: Theory of Computing Systems

Abstract

We consider sets Turing reducible to p-selective sets under various resource bounds and a 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 cannot be reduced to the p-selective sets under 2lin time reductions with at mostnk queries for anyfixed k ε N.