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.