Another proof that bpp?ph (and more)
Another proof that bpp?ph (and more)
复制标题
另一个证明 bpp?ph （以及更多）
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
Oded Goldreich;David Zuckerman
本文给出了BPP证明MA（φ PH）的Sipser-Lautemann定理的另一个证明.目前的证明是基于Zuckerman（1996）关于BPP放大的强有力的结果。鉴于这些结果，目前的证明甚至比以前的更简单。此外，扩展证明导致关于MA的两个结果：MA <$ZPPNP（这似乎是新的），并且双侧误差MA等于MA。最后，我们调查已知的事实，关于片段的多项式时间层次结构，包含MA。
We provide another proof of the Sipser-Lautemann Theorem by which BPP ⊆ MA (⊆ PH). The current proof is based on strong results regarding the amplification of BPP, due to Zuckerman (1996). Given these results, the current proof is even simpler than previous ones. Furthermore, extending the proof leads to two results regarding MA: MA ⊆ ZPPNP (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 that contains MA.