322
правки
Изменения
Нет описания правки
== Соотношение вероятностных классов ==
{{Теорема
|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 =
Покажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
Пусть программа <tex>p</tex> ошибается на словах из языка с вероятностью не более <tex>1/2</tex>, <tex>q</tex> ошибается на словах не из языка с аналогичной вероятностью. Вычислим значения <tex>p(x)</tex> и <tex>q(x)</tex>. Вернем <tex>0</tex>, если <tex>p(x) = 0</tex>. Вернем <tex>1</tex>, если <tex>q(x) = 1</tex>. В противном случае вернем <tex>?</tex>. Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p(x) = 1, q(x) = 0) \le 1/2</tex>.
Покажем, что <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — разрешающая программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
Достаточно взять <tex>\varepsilon < p_0 / 4</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью полиномиального количества вызовов ''random''(). Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.
}}
{{Теорема|statement =<tex>\mathrm{RP} \subset \mathrm{BPP}</tex>|proof =3. ...
}}
