هل مغلقة فئة BPP للاتحاد والتقاطع؟

Question

تماما مثل العنوان يقول.أريد أن أثبت أنه منح لغتين $ l_1، l_2 \ in bpp $ ، $ l_1 \ cup l_2 \ in bpp $ و $ l_1 \ cap l_2 \ in bpp $

Answer 1

دع $ t_1 $ (resp. $ t_2 $ $ 1/3 $ for $ l_1 $ (resp. $ l_2 $ ).

دع $ t'_1 $ (resp. $ t'_2 $ ) كن آلة تورينج ل $ l_1 $ (resp. $ l_2 $ ) التي تم الحصول عليها عن طريق تشغيل $ T_1 $ (resp. $ t_2 $ ) $ 9 $ times وإرجاع نتيجة الغالبية. خطأ احتمالية $ t'_1 $ (resp. $ t'_2 $ ) هو على الأكثر < Span Class="حاوية الرياضيات"> $ p_f=sum_ {i= 5} ^ 9 \ binom {i} {i} {i} (1/3) ^ i (2/3) ^ {9-i} <\ frac <\ frac {1} {6} $ .

آلة تورينج ل $ l_1 \ cup l_2 $ (resp. $ l_1 \ cap l_2 $ ) محاذاة $ t'_1 $ و $ t'_2 $ $ t'_1 $ و $ t'_2 $ قبول. من قبل الاتحاد ملزمة، احتمالية الخطأ في آلة Turing هذا هو على الأكثر $ 2 \ cdot p_f <2 \ cdot \ frac {1} {}=frac {1} {3 } $ .