205
правок
Изменения
м
→Теорема о соотношении классов \mathrm{coRP} и \Pi_1
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство<br/><tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>.<br/> Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}
== Теорема о соотношении классов <tex>\mathrm{coRP}</tex> и <tex>\Pi_1</tex> coNP ==
{{Теорема
|statement = <tex>\mathrm{coRP} \subset \Pi_1mathrm{coNP}</tex>.|proof = Рассмотрим язык <tex>L \in \mathrm{coRP} \Leftrightarrow \overline{L} \in \mathrm{RP} \Rightarrow \overline{L} \in \mathrm{NP} \Leftrightarrow L \in \mathrm{coNP} = \Pi_1</tex>.
}}
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
