Random Reductions in the Boolean Hierarchy are Not Robust.
Chang, Richard; Rohatgi, Pankaj
We investigate random reductions from complete sets in the Boolean Hierarchy to their complements. We show that under the assumption that the Polynomial Hierarchy is infinite, the error probability of such reductions cannot be significantly lower than a constant. This constant depends on the classes in question. Thus, random reductions in the Boolean Hierarchy are not robust. We also show that the trivial random reductions between classes at the second level of the Boolean Hierarchy are optimal.
computer science; technical report
Previously Published As