Ist die BPP-Klasse für Union und Kreuzung geschlossen?

Question

wie der Titel sagt.Ich möchte beweisen, dass es mit zwei Sprachen gibt $ l_1, l_2 \ in BPP $ , $ l_1 \ cup l_2 \ in BPP $ und $ l_1 \ cap l_2 \ in BPP $

Answer 1

let $ t_1 $ (bzw. $ t_2 $ ) eine probabilistische Turingmaschine mit Polynomialzeit mit Fehlerwahrscheinlichkeit von höchstens $ 1/3 $ für $ l_1 $ (bzw. $ l_2 $ ).

$ t'_1 $ (bzw. $ t'_2 $ ) Sei eine Turingmaschine für $ l_1 $ (bzw. $ l_2 $ ), die durch Ausführen von $ T_1 $ (bzw. $ t_2 $ ) $ 9 $ mal und zurücksenden Mehrheitsergebnis. Die Fehlerwahrscheinlichkeit von $ T'_1 $ (bzw. $ t'_2 $ ) ist höchstens < Span-Klasse="Math-Container"> $ p_f=sum_ {i= 5} ^ 9 \ Binom {9} {i} (1/3) ^ i (2/3) ^ {9-i} <\ frac {1} {6} $ .

A Turing Machine für $ l_1 \ cup l_2 $ (bzw. $ l_1 \ cap l_2 $ ) simuliert $ t'_1 $ und $ t'_2 $ und akzeptiert, ob und nur wenn mindestens eins von (bzw. beide von) $ t'_1 $ und $ t'_2 $ akzeptieren. Durch die Gebundene Union ist die Wahrscheinlichkeit des Fehlers dieser Turing-Maschine höchstens $ 2 \ CDOT P_F <2 \ CDOT \ FRAC {1} {6}=frac {1} {3 } $ .