La classe BPP è chiusa per unione e l'intersezione?

Question

Proprio come dice il titolo.Voglio dimostrare che data due lingue $ l_1, l_2 \ in BPP $ , $ l_1 \ tazza l_2 \ in BPP $ e $ l_1 \ cap l_2 \ in BPP $

Answer 1

Let $ T_1 $ (resp. $ T_2 $ ) una macchina probabilistica probabilistica polinomiale con Probabilità di errore di al massimo $ 1/3 $ per $ l_1 $ (resp. $ l_2 $ ).

Let $ t'_1 $ (resp. $ t'_2 $ ) Sii una macchina di Turing per $ l_1 $ (resp. $ l_2 $ ) ottenuto eseguendo $ T_1 $ (resp. $ t_2 $ ) $ 9 $ volte e restituire il risultato della maggioranza. La probabilità errore di $ t'_1 $ (resp. $ t'_2 $ ) è al massimo < Class Class="Math-Container"> $ p_f=sum_ {i= 5} ^ 9 \ binom {9} {i} (1/3) ^ i (2/3) ^ {9-I} <\ frac {1} {6} $ .

Una macchina di Turing per $ l_1 \ tazza l_2 $ (resp. $ l_1 \ cap l_2 $ ) simula $ t'_1 $ e $ t'_2 $ e accetta se e solo se almeno uno di (resp. entrambi) $ t'_1 $ e $ t'_2 $ Accetta. Dal punto di vista dell'Unione, la probabilità di errore di questa macchina di tentazione è al massimo $ 2 \ cdot p_f <2 \ cdot \ frac {1} {6}=frac {1} {3 } $ .