205
правок
Изменения
м
Нет описания правки
<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> =={{Теорема|statement = <tex>\mathrm{coRP} \subset \Pi_1</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>.}}
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
