Abstract:
SBP is a probabilistic promise class located between MA and AM \cap 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 with certain properties, BP \exists C contains every class defined by applying an operator sequence over {U, \exists, BP, SB} to C.