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 1/2 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 Sigma(P)(2). In the 2 same world. BPPpath is not contained in Sigma(P)(2), 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 . there exists . C contains every class defined by applying an operator sequence over {U., there exists(.), BP., SB.} to C. (c) 2006 Elsevier Inc. All rights reserved.