We consider separations of reducibilities by random sets. First, we show a
result on polynomial time-bounded reducibilities that query their oracle no
nadaptively: for every p-random set R, there is a set that is reducible to
R with k+1 queries but is not reducible to any other p-random set with at m
ost k queries. This result solves an open problem stated in a recent survey
paper by Lutz and Mayordomo [EATCS Bulletin, 68 (1999), pp. 64-80]. Second
, we show that the separation result above can be transferred from the sett
ing of polynomial time-bounds to a setting of rec-random sets and recursive
reducibilities. This extends the main result of Book, Lutz, and Martin [ I
nform. and Comput., 120 (1995), pp. 49-54] who, by using different methods,
showed a similar separation with respect to Martin-Lof-random sets. Moreov
er, in both settings we obtain similar separation results for truth-table v
ersus bounded truth-table reducibility.