Изменения

Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_{\mathrm{RPRP_{weak}}}</tex> равна <tex>(1-\frac{1}{q(|x|)})^k</tex>, то есть программа вероятность ошибки программы <tex>m_{\mathrm{RP_RP}}</tex> равна <tex>(1-\frac{weak}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>. Логарифмируя, получаем: <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_{weak}}\colon</tex><br/>Доказательство аналогично предыдущему пункту. <tex>m_{\mathrm{RP_{weak}}}(x)</tex> '''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже '''if''' <tex>m_{\mathrm{RP}}(x)</tex> '''then return''' <tex>1</tex> '''return''' <tex>0</tex>Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. Из него получается, что <tex>k > log_2(q(|x|))</tex>. 

Доказательство аналогично предыдущему пунктуНапишем программу <tex>m_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>. <tex>m_{\mathrm{RP_{strong}}}(x)</tex> '''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже '''if''' <tex>m_{\mathrm{RP}}(x)</tex> '''then return''' <tex>1</tex> '''return''' <tex>0</tex>В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}} \Leftrightarrow k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <tex>-log_{2}(1-\frac{1}{2^{q(|x|)}}) = \frac{2^{-q(|x|)}}{ln(2)} + o(2^{-q(|x|)}) = \frac{(1+q(|x|)+o(q(|x|)))^{ln(\frac{1}{2})}}{ln(2)} < \frac{1+q(|x|)}{ln(2)}</tex>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>. <tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex><br/>Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. <tex>m_{\mathrm{RP}}(x)</tex> '''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже '''if''' <tex>m_{\mathrm{RP_{strong}}}(x)</tex> '''then return''' <tex>1</tex> '''return''' <tex>0</tex><tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.