322
правки
Изменения
→Соотношение вероятностных классов
== Соотношение вероятностных классов ==
{{Теорема
|statement = <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
|proof =
Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, разрешающие <tex>\mathrm{P}</tex>, удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.
{{Теорема
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
Покажем, что <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в разрешающей программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу с ограничениями <tex>\mathrm{NP}</tex>, разрешающую <tex>L</tex>.
{{Теорема
|statement =
1. <tex>\mathrm{RP} \subset \mathrm{BPP}</tex>;<br>2. <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in RP</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.
Пусть <tex>x \notin L</tex>. Тогда <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}
== См. также ==
