On sets turing reducible to p-selective sets |
| |
Authors: | H. J. Burtschick W. Lindner |
| |
Affiliation: | 1. Fachbereich Informatik, TU - Berlin, Franklinstrasse 28/29, D-10587, Berlin, Germany 2. Abteilung Theoretische Informatik, Universit?t Ulm, Oberer Eselsberg 3, D-89069, Ulm, Germany
|
| |
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 2 lin time reductions with at mostn k queries for anyfixed k ε N. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|