RANDOM-SELF-REDUCIBILITY OF COMPLETE-SETS

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.