Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR03-069 | 13th August 2003 00:00

#### Small Bounded-Error Computations and Completeness

TR03-069
Authors: Elmar Böhler, Christian Glaßer, Daniel Meister
Publication: 10th September 2003 11:03
Downloads: 1203
Keywords:

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.

ISSN 1433-8092 | Imprint