322
правки
Изменения
→См. также
[[Категория: Теория сложности]]
'''Вероятностные вычисления ''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ , говоря неформально, к случайным битамгенератору случайных чисел. Мы рассмотрим классы сложности, для которых разрешающие программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
{{Определение
|definition =
'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов. Распределение битов на ленте , распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
}}
{{Определение
|definition =
'''Вероятностной машиной Вероятностная машина Тьюринга''' будем называть машину (ВМТ) — детерминированная машина Тьюринга, имеющее доступ к имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной лентеленты.
}}
{{Теорема
|statement =1. <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>2. <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>3. <tex>\mathrm{RP} \subset \mathrm{BPP}</tex>|proof =1. Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, разрешающие <tex>\mathrm{P}</tex>, удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.<br>Покажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>....<br>2. Покажем, что <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в разрешающей программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу с ограничениями <tex>\mathrm{NP}</tex>, разрешающую <tex>L</tex>.<br>Покажем, что <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>pm</tex> — разрешающая программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное времяВМТ. Тогда программа для любых <tex>\mathrm{PS}x</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>pA</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости — предиката от того, каких ответов <tex>pm</tex> оказалось больше.<br>Теперь докажем, что выполняется <tex>R = \mathrm{NP} r \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>\mathrm{PP}</tex>, которая разрешает <tex>L \in \mathrm{NP}</tex>. Пусть функция ''infair_coin''() моделирует нечестную монету, а именно возвращает единицу с вероятностью <tex>1/2 - \varepsilon</tex>, где <tex>\varepsilon</tex> мы определим позже, и ноль с вероятностью <tex>1/2 + \varepsilon</tex>. Пусть также <tex>V</tex> — верификатор сертификатов для <tex>L</tex>. Тогда <tex>q</tex> будет выглядеть следующим образом: qbigm| A(x): c <- случайный сертификат (полиномиальной длины) '''return''' Vm(x, cr) ? 1 : infair_coin()Необходимо удовлетворить условию <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>. Пусть <tex>x \notin LSigma</tex>, т. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монетые. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2R</tex>измеримо.|proof=Пусть <tex>x R = \in L</tex>. Тогда по формуле полной вероятности <tex>bigcup\operatornamelimits_{Pi = 0}(p(x) = 1) = p_0 + (1 - p_0) (1/2 - ^\varepsilon)infty R_i</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку все сертификаты имеют полиномиальную длину и существует хотя бы один правильный сертификат, <tex>p_0</tex> не более чем экспоненциально мала. Найдем <tex>R_i = \varepsilon</tex> из неравенства <tex>{r \operatorname{P}bigm| A(pm(x, r) = 1) > 1/2, m</tex>: прочитала ровно <tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2i</tex>; <tex>p_0 / 2 + (p_0 - 1)\varepsilon > 0</tex>; первых символов с <tex>r\varepsilon < p_0 (1 - p_0) / 2</tex>. Достаточно взять <tex>\varepsilon < p_0 / 4}</tex>. Из сделанного выше замечания следуетЭто верно, что работу функции ''infair_coin''() можно смоделировать с помощью полиномиального количества вызовов ''random''()поскольку мы рассматриваем только завершающиеся ВМТ. Таким образомКроме того, мы построили программу из определения <tex>qR_i</tex>следует, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>что они дизъюнктны.
<tex>R_i \in \Sigma</tex> как зависящие от <tex>i</tex> первых битов вероятностной ленты, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>.
}}
== См. также ==
* [[Теоремы о BPP, BPPweak Классы RP и BPPstrongcoRP]]* [[Уменьшение ошибки в классе RPКласс ZPP]]* [[Теорема ЛаутеманаКласс BPP]]
== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/book.pdf Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]