Random-self-reducibility of complete sets
J Feigenbaum, L Fortnow - SIAM Journal on Computing, 1993 - SIAM
SIAM Journal on Computing, 1993•SIAM
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 MOD_mP are random-self-reducible.
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 MOD_mP are random-self-reducible.
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 are random-self-reducible.