A classe BPP é fechada para união e interseção?

Question

Assim como o título diz.Eu quero provar que dadas duas línguas $ l_1, l_2 \ in bpp $ , $ l_1 \ cope l_2 \ in bpp $ e $ l_1 \ cap l_2 \ em bpp $

Answer 1

Deixe $ t_1 $ (resp. $ t_2 $ ) uma máquina de Turing probabilista de tempo polinômio com Probabilidade de erro no máximo $ 1/3 $ para $ l_1 $ (resp. $ l_2 $ ).

Deixe $ t'_1 $ (resp. $ t'_2 $ ) seja uma máquina de Turing Para $ l_1 $ (resp. $ l_2 $ ) obtido por execução $ T_1 $ (resp. $ t_2 $ ) $ 9 $ vezes e retornar o resultado da maioria. A probabilidade de erro $ t'_1 $ (resp. $ t'_2 $ ) é no máximo < span class="contentor de matemática"> $ p_f=sum_ {i= 5} ^ 9 \ binom {9} {i} (1/3) ^ i (2/3) ^ {9-I} <\ frac {1} {6} $ .

uma máquina de Turing para $ l_1 \ cope l_2 $ (resp. $ l_1 \ tampa l_2 $ ) simula $ t'_1 $ e $ t'_2 $ e aceita se e somente se pelo menos um de (resp. ambos) $ t'_1 $ e $ t'_2 $ aceite. Pelo sindicato ligado, a probabilidade de erro desta máquina de Turing está no máximo $ 2 \ CDot P_F <2 \ Cdot \ Frac {1} {6}=frac {1} {3 } $ .