205
правок
Изменения
→Теорема об эквивалентности определений
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex><br/>Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>.<br/>
}}
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
