¿Está cerrada la clase BPP para la unión y la intersección?

Question

Al igual que el título dice.Quiero probar que le dan dos idiomas $ l_1, l_2 \ in bpp $ , $ l_1 \ taza l_2 \ en bpp $ y $ l_1 \ tapa l_2 \ in bpp $

Answer 1

Let $ t_1 $ (resp. $ t_2 $ ) una máquina de trabajo probabilística de tiempo polinomial con Probabilidad de error de la mayoría de $ 1/3 $ para $ l_1 $ (resp. $ l_2 $ ).

Let $ t'_1 $ (resp. $ t'_2 $ ) ser una máquina de Turing para $ l_1 $ (resp. $ l_2 $ ) obtenido ejecutando $ T_1 $ (resp. $ t_2 $ ) $ 9 $ veces y devolviendo el resultado de la mayoría. La probabilidad de error de $ t'_1 $ (resp. $ t'_2 $ ) es como máximo < Span Class="Math-contenedor"> $ P_F=Sum_ {i= 5} ^ 9 \ binom {9} {i} (1/3) ^ i (2/3) ^ {9-i} <\ frac {1} {6} $ .

Una máquina de Turing para $ l_1 \ taza l_2 $ (resp. $ l_1 \ tapa l_2 $ ) simula $ t'_1 $ y $ t'_2 $ y acepta si es al menos uno de (resp. ambos de) $ t'_1 $ y $ t'_2 $ Aceptar. Por la Unión Ubicado, la probabilidad de error de esta máquina de Turing está en la mayoría de $ 2 \ cdot p_f <2 \ cdot \ frac {1} {6}=frac {1} {3 } $ .