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