The global power of additional queries to p-random oracles

Authors
Citation
W. Merkle, The global power of additional queries to p-random oracles, SIAM J COMP, 31(2), 2001, pp. 483-495
Citations number
27
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
483 - 495
Database
ISI
SICI code
0097-5397(20011011)31:2<483:TGPOAQ>2.0.ZU;2-1
Abstract
We consider separations of reducibilities by random sets. First, we show a result on polynomial time-bounded reducibilities that query their oracle no nadaptively: for every p-random set R, there is a set that is reducible to R with k+1 queries but is not reducible to any other p-random set with at m ost k queries. This result solves an open problem stated in a recent survey paper by Lutz and Mayordomo [EATCS Bulletin, 68 (1999), pp. 64-80]. Second , we show that the separation result above can be transferred from the sett ing of polynomial time-bounds to a setting of rec-random sets and recursive reducibilities. This extends the main result of Book, Lutz, and Martin [ I nform. and Comput., 120 (1995), pp. 49-54] who, by using different methods, showed a similar separation with respect to Martin-Lof-random sets. Moreov er, in both settings we obtain similar separation results for truth-table v ersus bounded truth-table reducibility.