La classe BPP est-elle fermée pour l'union et l'intersection?

Question

Tout comme le titre dit.Je veux prouver que donner deux langues $ l_1, l_2 \ \ \ \ \ \ in bpp $ , $ l_1 \ tasse l_2 \ in bpp $ et $ l_1 \ cap l_2 \ in bpp $

Answer 1

laissez $ t_1 $ (resp. $ t_2 $ ) une machine de diurcine probabiliste polynomiale avec probabilité d'erreur de 1/3 $ pour $ l_1 $ (resp. $ l_2 $ ).

let $ t'_1 $ (resp. $ t'_2 $ ) être une machine de Turing pour $ l_1 $ (resp. $ l_2 $ ) obtenu en exécutant $ T_1 $ (resp. $ t_2 $ ) $ 9 $ $ t'_1 $ (resp. $ t'_2 $ ) est au plus < span class="math-conteneur"> $ p_f=sum_ {i= 5} ^ 9 \ binom {9} {i} (1/3) ^ i (2/3) ^ {9-i} <\ frac {1} {6} $ .

Une machine de Turing pour $ l_1 \ tasse l_2 $ (resp. $ l_1 \ cap l_2 $ ) simule $ t'_1 $ et $ t'_2 $ et accepte si et seulement si au moins un de (resp. les deux) $ t'_1 $ et $ t'_2 $ accepte. Par le syndicat lié, la probabilité d'erreur de cette machine de Turing est au plus 2 \ CDOT P_F <2 \ CDOT \ frac {1} {6}=frac {1} \ frac {1} {3 } $ .