Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-069 | 13th August 2003 00:00

Small Bounded-Error Computations and Completeness

RSS-Feed




TR03-069
Authors: Elmar Böhler, Christian Glaßer, Daniel Meister
Publication: 10th September 2003 11:03
Downloads: 3043
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