archives

The Global Power of Additional Queries to Random Oracles


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

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.

Full text available as:Postscript
Adobe PDF

Abstract

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),
k-tt				   (k+1)-tt
where RAND is the set of all algorithmically random languages.

Subjects:All uncategorized technical reports
ID code:00000040
Deposited by:Staff Account on 09 February 1993



Contact site administrator at: ssg@cs.iastate.edu