Изменения

<tex>\mbox{BPP} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > \frac{2}{3} \}</tex>

Так же еще Также существуют два [[Класс BPP|эквивалентных]] определения <tex>BPP</tex>:*<tex>\mbox{BPP}_{weak} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > \frac{1}{2} + 1/p(|x|)\}</tex>, где <tex>m</tex> - [[Вероятностная машина Тьюринга|ВМТ]], а <tex>p(|x|): \forall x: ~ p(|x|) > 2</tex> - полином.*<tex>\mbox{BPP}_{strong} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > 1 - 2^{-p(|x|)}\}</tex>, где <tex>m</tex> -[[Вероятностная машина Тьюринга|ВМТ]], а <tex>p(|x|)</tex> - полином.  Число <tex>\frac{2}{3}</tex> в определении выбрано произвольно: если вместо него выбрать любое число, строго большее <tex>\frac{1}{2}</tex>, то получится тот же самый класс. Это верно, поскольку если есть машина Тьюринга, распознающая язык с вероятностью ошибки <tex>p</tex>, то точность можно сколь угодно хорошо улучшить за счёт относительно небольшого прироста времени. Если мы запустим машину <tex>k=|x|</tex> раз подряд, а в качестве результата возьмём результат большинства запусков, то вероятность ошибки упадёт до <tex>\left(2 \sqrt{p(1-p)} \right)^k</tex>, а время останется равным <tex>poly(|x|)</tex>. Здесь <tex>k</tex> запусков машины рассматриваются как схема Бернулли с <tex>k</tex> испытаниями и вероятностью успеха <tex>1-p</tex>, а формула, выражающая ошибку, — вероятность неудачи не менее чем в половине случаев. Если теперь запустить машину <tex>k^{2}</tex> раз подряд, то время все еще будет <tex>poly(|x|)</tex>, а вероятность ошибки упадёт до <tex>\left(2 \sqrt{p(1- p)} \right)^{k^2}</tex>. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения. ==Эквивалентность определений==Требуется доказать, что <tex>BPP_{strong} = BPP= BPP_{weak}</tex>.<br>Для доказательства обоих равенств потребуется неравенство Чернова:<br><center><tex>\forall p > 1/2: \sum_{\mathcal{b}\frac{n}{2}\mathcal{c}+1}^{n}[{{{n\choose i}} p^{i}(1-p)^{n-i}] \geq 1 - e^{-2n(p-1/2)^2}}</tex></center> ===Доказательство <tex>BPP_{strong} = BPP</tex>===Очевидно, что <tex>BPP_{strong} \subset BPP</tex>.<br>Докажем обратное включение. Пусть <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 \subset BPP_{strong} \Rightarrow BPP_{strong} = BPP</tex>.====Построение <tex>m_{2}</tex>====Машина <tex>m_{2}</tex> будет работать таким образом:запустим <tex>N_{str}(p(|x|),m_{1})</tex> раз машину <tex>m_{1}</tex>, запоминая результат каждого запуска.Вернем <tex>1</tex>, если больше половины запусков вернули <tex>1</tex>. Иначе вернем <tex>0</tex>.Если <tex>N_{str}</tex> таково, что <tex>P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)} \wedge N_{str} \in poly(|x|)</tex>, то искомая машина построена.=====Построение <tex>N_{str}(p|x|,m_{1})</tex>=====При запуске машины <tex>m_{2}</tex> все запуски <tex>m_{1}</tex> можно считать независимыми, причем каждый запуск<tex>m_{1}</tex> возвращает правильный ответ с вероятностью <tex>p \geq 2/3 > 1/2</tex>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <tex>P(m_{2}(x) = [x \in L])</tex> :<br><tex>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{str}}{2}\mathcal{c}+1}^{N_{str}}[{N_{str}\choose i} p^{i}(1-p)^{N_{str}- полиномi}]</tex>. Тогда, по неравенству Чернова: <tex>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{str}(p-1/2)^2}</tex>. Достаточно подобрать такое <tex>N_{str}</tex>, чтобы <tex>1 - e^{-2N_{str}(p-1/2)^2} \geq 1 - 2^{-p(|x|)}</tex>. Несложными преобразованиями получаем <tex>N_{str} \geq \frac{p(|x|) \ln 2}{2(p-1/2)^2}</tex>, т.е.можем выбрать <tex>N_{str} \in poly(|x|)</tex>

Число ===Доказательство <tex>BPP_{weak} = BPP</tex>===Очевидно, что <tex>BPP \fracsubset BPP_{2weak}</tex>.<br>Докажем обратное включение. Пусть <tex>L \in BPP_{3weak}</tex> в определении выбрано произвольно: если вместо него выбрать любое число, строго большее тогда существует[[Вероятностная машина Тьюринга|ВМТ]] <tex>m_{1}: T(m_{1},x) = Poly(|x|) \fracwedge 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} \subset BPP \Rightarrow BPP_{weak} = BPP</tex>. Если мы ====Построение <tex>m_{2}</tex>====Машина <tex>m_{2}</tex> будет работать таким образом:запустим <tex>N_{weak}(p(|x|),m_{1})</tex> раз машину <tex>km_{1}</tex> раз подряд, а в качестве результата возьмём запоминая результат большинства каждого запуска.Вернем <tex>1</tex>, если больше половины запусковвернули <tex>1</tex>. Иначе вернем <tex>0</tex>.Если <tex>N_{weak}</tex> таково, то вероятность ошибки упадёт до что <tex>\leftP(m_{2 }(x) = [x \sqrtin L]) > 2/3) \wedge N_{p(1-p)weak} \rightin poly(|x|)^k</tex>, а время останется равным то искомая машина построена.=====Построение <tex>polyN_{weak}(p|x|,m_{1})</tex>. Здесь =====При запуске машины <tex>m_{2}</tex> все запуски <tex>km_{1}</tex> запусков машины рассматриваются как схема Бернулли с можно считать независимыми, причем каждый запуск<tex>km_{1}</tex> испытаниями и возвращает правильный ответ с вероятностью успеха <tex>p = 1-/2 + 1/p(|x|) > 1/2</tex>. Тогда по схеме Бернулли вероятность того, а формула, выражающая ошибкучто больше половины запусков вернули правильный ответ, — вероятность неудачи не менее чем в половине случаевт. Если теперь запустить машину е <tex>k^P(m_{2}(x) = [x \in L])</tex> раз подряд, то время все еще будет :<br><tex>polyP(m_{2}(|x|)= [x \in L]) = \sum_{\mathcal{b}\frac{N_{weak}}{2}\mathcal{c}+1}^{N_{weak}}[{N_{weak}\choose i} p^{i}(1-p)^{N_{weak}-i}]</tex>. Тогда, а вероятность ошибки упадёт до по неравенству Чернова: <tex>\leftP(m_{2 }(x) = [x \sqrtin L]) \geq 1 - e^{-2N_{weak}(p(-1/2)^2}</tex>. Достаточно подобрать такое <tex>N_{weak}</tex>, чтобы <tex>1-e^{-2N_{weak}(p-1/2)^2} \geq 2/3</tex>. Несложными преобразованиями получаем <tex>N_{weak} \rightgeq \frac{\ln 3}{2(1/2 +1/p(|x|)-1/2)^2} = \frac{kp(|x|)^2 \ln 3}{2}</tex>, т.е. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значенияможем выбрать <tex>N_{weak} \in poly(|x|)</tex>.