Изменения
Нет описания правки
{{Лемма
| statement = <tex>\mathrm{BPP} = \mathrm{coBPP}</tex>
| proof =
Рассмотрим <tex>L \in \mathrm{BPP}</tex>. Существует такая программа <tex>p</tex>, что <tex>P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Покажем, что <tex>\overline{L} \in \mathrm{BPP}</tex>. Для этого рассмотрим следующую программу:
<tex>p'(x)</tex> <tex>\{</tex>
<tex>return (1 - p(x));</tex>
<tex>\}</tex>
<tex>P(p'(x) = [x \in \overline{L}]) = P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Таким образом <tex>\overline{L} \in \mathrm{BPP}</tex>.
#<tex>L \in \mathrm{BPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{coBPP}</tex>. Получаем <tex>\mathrm{BPP} \subset \mathrm{coBPP}</tex>.
#<tex>L \in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}</tex>. Получаем <tex>\mathrm{coBPP} \subset \mathrm{BPP}</tex>.
}}
==Теорема==
{{ Теорема
