Show simple item record

AuthorBurtschick, Hans-Jörgdc.contributor.author
AuthorLindner, Wolfgangdc.contributor.author
Date of accession2016-03-15T09:03:42Zdc.date.accessioned
Available in OPARU since2016-03-15T09:03:42Zdc.date.available
Year of creation1995dc.date.created
AbstractWe 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.dc.description.abstract
Languageendc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseStandarddc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/license_v3dc.rights.uri
Dewey Decimal GroupDDC 004 / Data processing & computer sciencedc.subject.ddc
LCSHComputational complexitydc.subject.lcsh
TitleOn sets Turing reducible to p-selective setsdc.title
Resource typeBerichtdc.type
DOIhttp://dx.doi.org/10.18725/OPARU-2443dc.identifier.doi
PPN1651705143dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-vts-81756dc.identifier.urn
GNDBerechnungskomplexitätdc.subject.gnd
FacultyFakultät für Ingenieurwissenschaften und Informatikuulm.affiliationGeneral
Date of activation2012-09-07T23:05:48Zuulm.freischaltungVTS
Peer reviewneinuulm.peerReview
Shelfmark print versionQAA 5/A4.95,9uulm.shelfmark
DCMI TypeTextuulm.typeDCMI
VTS-ID8175uulm.vtsID
CategoryPublikationenuulm.category
Ulm seriesUlmer Informatik-Berichteuulm.seriesUlmName
University Bibliographyjauulm.unibibliographie


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record