On sets Turing reducible to p-selective sets
Bericht
Authors
Burtschick, Hans-Jörg
Lindner, Wolfgang
Faculties
Fakultät für Ingenieurwissenschaften und InformatikUlm serial
Ulmer Informatik-Berichte
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.
Date created
1995
Subject Headings
Berechnungskomplexität [GND]Computational complexity [LCSH]
Dewey Decimal Group
DDC 004 / Data processing & computer scienceMetadata
Show full item recordCitation example
Burtschick, Hans-Jörg; Lindner, Wolfgang (2012): On sets Turing reducible to p-selective sets. Open Access Repositorium der Universität Ulm. http://dx.doi.org/10.18725/OPARU-2443