205
правок
Изменения
→Теорема об эквивалентности определений
<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/>
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex><br/>
Доказательство такое же, как в предыдущем пункте.<br/>
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex><br/>
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>m_{\mathrm{RP}}(x)</tex>
<tex>f = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>false</tex>
<tex>t = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>true</tex>
'''for''' <tex>i = 1 \ldots k</tex>
'''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
'''then''' <tex>f = f + 1</tex>
'''else''' <tex>t = t + 1</tex>
'''return''' <tex>f > t \ ? \ false : true</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>false</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. <tex>k</tex> надо выбрать таким, что вероятность ошибки программы <tex>m_{\mathrm{RP}}(x)</tex> при <tex>x \in L</tex> была меньше <tex>\frac {1}{2}</tex>. Вероятность ошибки программы равна <tex>(1-\frac{1}{q(|x|)})^k</tex>. Получается неравенство <tex>(1-\frac{1}{q(|x|)})^k < \frac{1}{2}</tex>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex><br/>
}}
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
