BPP类是否已关闭联盟和交叉路口？

Question

就像标题说。我想证明，给定的两种语言 $ l_1，l_2 \在bpp $ ， $ l_1 \ cup l_2 \以bpp $和 $ l_1 \ cap l_2 \在bpp $

中

Answer 1

let $ t_1 $ （resp。 $ t_2 $ ）多项式时间概率图定型误差概率为大多数 $ 1/3 $ $ l_1 $ （resp。 $ l_2 $ ）。

let $ t'_1 $ （resp。 $ t'_2 $ ）是一个图定机器for $ l_1 $ （resp。 $ l_2 $ ）通过运行 $ t_1 $ （resp。 $ t_2 $ ） $ 9 $ 时间并返回大多数结果。 $ t'_1 $ （resp。 $ t'_2 $ ）最多<跨越类=“math-container”> $ p_f=sum_ {i= 5} ^ 9 \ binom {9} {i}（1/3）^ i（2/3）^ {9-i} <\ frac {1} {6} $ 。

$ l_1 \ cup l_2 $ （resp。 $ l_1 \ cap l_2 $ ）模拟 $ t'_1 $ 和 $ t'_2 $ ，并且仅在至少一个（resp。两个） $ t'_1 $ 和 $ t'_2 $ 接受。 由Union绑定，这个图灵机的错误概率最多是大多数 $ 2 \ cdot p_f <2 \ cdot \ frac {1} {3}=frac {1} {3 $ 。