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: 2854
Keywords: 


Abstract:




ISSN 1433-8092 | Imprint