This paper generalizes the previous formal definitions of random-self-
reducibility. It is shown that, even under a very general definition,
sets that are complete for any level of the polynomial hierarchy are n
ot nonadaptively random-self-reducible, unless the hierarchy collapses
. In particular, NP-complete sets are not nonadaptively random-self-re
ducible, unless the hierarchy collapses at the third level. By contras
t, we show that sets complete for the classes PP and MOD(m)P are rando
m-self-reducible.