Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-045 | 29th September 1997 00:00

Another proof that BPP subseteq PH (and more).

RSS-Feed

Abstract:


We provide another proof of the Sipser--Lautemann Theorem
by which BPP\subseteq MA (\subseteq PH).
The current proof is based on strong
results regarding the amplification of BPP, due to Zuckerman.
Given these results, the current proof is even simpler than previous ones.
Furthermore, extending the proof leads to two results regarding MA:
MA\subseteq ZPP^NP (which seems to be new),
and that two-sided error MA equals MA.
Finally, we survey the known facts regarding the fragment of
the polynomial-time hierarchy which contains MA.


Comment(s):

Comment #1 to TR97-045 | 16th June 1998 14:34

Comment Comment on: TR97-045





Comment #1
Authors: Peter Bro Miltersen
Accepted on: 16th June 1998 14:34
Downloads: 2979
Keywords: 


Abstract:




ISSN 1433-8092 | Imprint