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 locate SBP 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 ∑_2~p. We provide a new characterization of BPP_(path). This characterization shows that SBP is a subset of BPP_(path). Consequently, there is an oracle relative to which BPP_(path) is not contained in ∑_2~p
展开▼
