Изменения

Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. <tex>m_p_{\mathrm{RP}}(x)</tex>

'''if''' <tex>m_p_{\mathrm{RP_{weak}}}(x)</tex>'''then''' '''then return''' <tex>1</tex>

Если слово <tex>x \notin L</tex>, то <tex>m_p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_p_{\mathrm{RP_{weak}}}</tex> равна меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>m_p_{\mathrm{RP}}</tex> равна меньше, чем <tex>(1-\frac{1}{q(|x|)})^k</tex>. <tex>k</tex> надо выбрать таким, что вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> при <tex>x \in L</tex> была меньше <tex>\frac {1}{2}</tex>. Получается неравенство <tex>(1-\frac{1}{q(|x|)})^k < \frac{1}{2}</tex>. Логарифмируя, получаем: <br/> <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. <br/> Разложив логарифм в ряд Тейлора, получаем <br/> <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>m_p_{\mathrm{RP_{weak}}}(x)</tex>

'''if''' <tex>m_p_{\mathrm{RP}}(x)</tex>'''then''' '''then return''' <tex>1</tex>

Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <br/> <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. Из него получается, что <tex>\Leftrightarrow k > log_2(q(|x|))</tex>.