ECCC-Report TR03-069https://eccc.weizmann.ac.il/report/2003/069Comments and Revisions published for TR03-069en-usWed, 10 Sep 2003 11:03:56 +0300
Paper TR03-069
| Small Bounded-Error Computations and Completeness |
Elmar Böhler,
Christian Glaßer,
Daniel Meister
https://eccc.weizmann.ac.il/report/2003/069SBP 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.
Wed, 10 Sep 2003 11:03:56 +0300https://eccc.weizmann.ac.il/report/2003/069