• English
    • Deutsch
View Item 
  •   OPARU Home
  • Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
  • Publikationen
  • View Item
  •   OPARU Home
  • Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
  • Publikationen
  • View Item
  • English 
    • English
    • Deutsch
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.

On sets Turing reducible to p-selective sets

Thumbnail
Download
vts_8175_11943.pdf (998.3Kb)
15 S.
 
Veröffentlichung
2012-09-07
DOI
10.18725/OPARU-2443
Bericht


Authors
Burtschick, Hans-Jörg
Lindner, Wolfgang
Faculties
Fakultät für Ingenieurwissenschaften und Informatik
Ulm serial
Ulmer Informatik-Berichte
License
Standard
https://oparu.uni-ulm.de/xmlui/license_v3
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 science

Metadata
Show full item record

Citation 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

Other citation formats



About OPARU | Contact Us
Impressum | Privacy statement
 

 

Advanced Search

Browse

All of OPARUCommunities & CollectionsFacultiesInstitutionsPersonsResource typesUlm SerialsDewey Decimal ClassesFundingThis CollectionFacultiesInstitutionsPersonsResource typesUlm SerialsDewey Decimal ClassesFunding

My Account

LoginRegister

Statistics

View Usage Statistics

About OPARU | Contact Us
Impressum | Privacy statement