|Abstract of Paper|
Error-Bounded Probabilistic Computations between MA and AM
by Elmar Boehler, Christian Glasser, and Daniel Meister
We introduce the probabilistic complexity class SBP. This class emerges from BPP by keeping the promise of a probability gap but decreasing the probability limit to exponentially small values. We show that SBP is in the polynomial-time hierarchy, more precisely, between MA and AM. We provide evidence that SBP does not coincide with these and other known complexity classes. We construct an oracle relative to which SBP is not contained in the second level of the polynomial-time hierarchy. We provide a new characterization of BPPpath. This characterization shows that SBP is a subset of BPPpath. Consequently, there is an oracle relative to which BPPpath is not contained in the second level of the polynomial-time hierarchy. This solves an open question raised by Han, Hemaspaandra, and Thierauf.