__
TR99-034 | 30th August 1999 00:00
__

#### The global power of additional queries to p-random oracles.

**Abstract:**

We consider separations of reducibilities in the context of

resource-bounded measure theory. First, we show a result on

polynomial-time bounded reducibilities: for every p-random set R,

there is a set which is reducible to R with k+1 non-adaptive

queries, but is not reducible to any other p-random set with at

most k non-adaptive queries. This result solves an open problem

stated in a recent survey paper by Lutz and Mayordomo in the

EATCS-Bulletin 68, 1999.

Second, we show that the separation result above can be transferred

from the setting of polynomial time bounds to a setting of

rec-random sets and recursive reducibilities. This yields as a

special case the main result of a paper by Book, Lutz, and Martin

(Information and Computation 120:49-54,1995 and STACS 1994)

who, by using different methods, showed a similar separation

w.r.t. Martin-L\"{o}f-random sets. Moreover, in both settings

we obtain a separation as above of truth-table versus bounded

truth-table reducibility.