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