Small Bounded-Error Computations and Completeness
Elmar Böhler, Christian Glaßer, Daniel Meister · 2003
Abstract SBP is a probabilistic promise class located between MA and AM∩BPPpath. The first part of the paper studies the question of whether SBP has many-one complete sets. We relate this question to the existence of uniform enumerations. We construct an oracle relative to which SBP and AM do not have many-one complete sets. In the second part we introduce the operator SB·. We prove that, for any class C, BP·∃·C contains every class defined by applying an operator sequence over{U·, ∃·, BP·, SB·} to C. 1