Error-bounded probabilistic computations between MA and AM

摘要

We introduce the probabilistic class SBP. This class emerges from BPP by keeping the promise of a probability gap but decreasing the probability limit from 12 to exponentially small values. We show that SBP is in the polynomial-time hierarchy, between MA and AM on the one hand and between BPP and BPPpath on the other hand. We provide evidence that SBP does not coincide with these and other known complexity classes. In particular, in a suitable relativized world SBP is not contained in Σ2P. In the same world, BPPpath is not contained in Σ2P, which solves an open question raised by Han, Hemaspaandra, and Thierauf. We study the question of whether SBP has many-one complete sets. We relate this question to the existence of uniform enumerations and construct an oracle relative to which SBP and AM do not have many-one complete sets. We introduce the operator SB⋅ and prove that, for any class C with certain properties, BP⋅∃⋅C contains every class defined by applying an operator sequence over {U⋅,∃⋅,BP⋅,SB⋅} to C.