THE GLOBAL POWER OF ADDITIONAL QUERIES TO RANDOM ORACLES

Authors
BOOK RV LUTZ JH MARTIN DM
Citation
Rv. Book et al., THE GLOBAL POWER OF ADDITIONAL QUERIES TO RANDOM ORACLES, Information and computation, 120(1), 1995, pp. 49-54
Citations number
17
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
120
Issue
1
Year of publication
1995
Pages
49 - 54
Database
ISI
SICI code
0890-5401(1995)120:1<49:TGPOAQ>2.0.ZU;2-Z
Abstract
It is shown that, for every k greater than or equal to O and every fix ed algorithmically random language B, there is a language that is poly nomial-time, truth-table reducible in k + 1 queries to B but not truth -table reducible in k queries in any amount of time to any algorithmic ally random language C. In particular, this yields the separation P-k- tt(RAND) not subset of or equal to P-(k+1-tt)(RAND), where RAND is the set of all algorithmically random languages. (C) 1995 Academic Press, Inc.