期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
