36
правок
Изменения
Нет описания правки
Докажем обратное включение. Пусть <tex>L \in BPP_{weak}</tex>, тогда существует
[[Вероятностная машина Тьюринга|ВМТ]] <tex>m_{1}: T(m_{1},x) = Poly(|x|) \wedge P(m_{1}(x) = [x \in L]) > 1/2 + 1/p(|x|)</tex>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <tex>m_{2}: T(m_{2},x) = Poly(|x|) \wedge P(m_{2}(x) = [x \in L]) >2/3</tex>,
используя заданные <tex>m_{1}</tex> и <tex>p(|x|)</tex>. Если нам это удастся, то <tex>L \in BPP \Rightarrow BPP_{weak} \in subset BPP \Rightarrow BPP_{weak} = BPP</tex>.
====Построение <tex>m_{2}</tex>====
Машина <tex>m_{2}</tex> будет работать таким образом:
