The global power of additional queries to \(p\)-random oracles (Q2784467)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The global power of additional queries to \(p\)-random oracles |
scientific article; zbMATH DE number 1732355
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The global power of additional queries to \(p\)-random oracles |
scientific article; zbMATH DE number 1732355 |
Statements
23 April 2002
0 references
separation of reducibilities
0 references
random sets
0 references
effective measure
0 references
resource-bounded reducibilities
0 references
effective reducibilities
0 references
bounded truth-table reducibility
0 references
random oracles
0 references
query complexity
0 references
resource bounded measure
0 references
The global power of additional queries to \(p\)-random oracles (English)
0 references
In this paper several separations of reducibilities with respect to random sets are considered. For polynomial-time reducibilities that query oracle nonadaptively it is shown that for any \(p\)-random set \(R\), there is a set that is polynomial-time-bounded reducible with \(k+1\) queries, but is not reducible to any other \(p\)-random set with at most \(k\) queries. This result solves a question left open by a recent paper of Lutz and Mayordomo. Further, it is shown that the separation above can be transferred from the setting of polynomial-time bounds to a setting of recursively random sets and recursive reducibilities. This extends a main result of \textit{R. V. Book}, \textit{J. H. Lutz} and \textit{D. M. Martin jun.} [Inf. Comput. 120, 49-54 (1995; Zbl 0835.68044)].
0 references
