Another proof that BPP subseteq PH (and more).

摘要

We provide another proof of the Sipser--Lautemann Theorem by which BPPMA (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: MAZPPNP (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.