Изменения

Перейти к: навигация, поиск

Сложностный класс BPP

5 байт добавлено, 14:15, 17 июня 2010
м
Построение m_{2}
Докажем обратное включение. Пусть <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> будет работать таким образом:
запустим <tex>N_{strweak}(p(|x|),m_{1})</tex> раз машину <tex>m_{1}</tex>, запоминая результат каждого запуска.
Вернем <tex>1</tex>, если больше половины запусков вернули <tex>1</tex>. Иначе вернем <tex>0</tex>.
Если <tex>N_{weak}</tex> таково, что <tex>P(m_{2}(x) = [x \in L]) > 2/3) \wedge N_{weak} \in poly(|x|)</tex>, то искомая машина построена.
33
правки

Навигация