Abstract of Paper

Error-Bounded Probabilistic Computations between MA and AM
by Elmar Boehler, Christian Glasser, and Daniel Meister

Abstract:

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.