The Power of Adaptiveness and Additional Queries in Random-Self-Reductions

We look at relationships between adaptive and nonadaptive random- self- reductions. We also look at what happens to random-self-reductions if we restrict the number of queries they are allowed to make. We show the following results: There exist sets that are adaptively random- self- reducible but not nonadaptively random-self-reducible. Under reasonable assumptions, there exist such sets in NP. There exists a function that has a nonadaptive (k+1)-random-self-reduction but does not have an adaptive k-random-self-reduction.