Random-Self-Reducibility of Complete Sets
Joan Feigenbaum, Lance Fortnow · SIAM Journal on Computing · 1993
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 not nonadaptively random-self-reducible, unless the hierarchy collapses. In particular, NP-complete sets are not nonadaptively random-self-reducible, unless the hierarchy collapses at the third level. By contrast, we show that sets complete for the classes PP and ${\text{MOD}}_m {\text{P}}$ are random-self-reducible.