Lutz, Jack H. and Martin, David M. Jr. (1993) The Global Power of Additional Queries to Random Oracles. Technical Report TR92-37, Department of Computer Science, Iowa State University.
The Global Power of Additional Queries to Random Oracles
Jack. H. Lutz and David M. Martin Jr.
Department of Computer Science
Iowa State University
Ames, Iowa 50011
It is shown that, for every k>0 and every fixed algorithmically random
language B, there is a language that is polynomial-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* algorithmically random
language C. In aprticular, this yields the separation
P (RAND) is a proper subset of P (RAND),
where RAND is the set of all algorithmically random languages.
Contact site administrator at: email@example.com