Изменения

Классы языков '''RP ''' и '''coRP ''' определяются следующим образом:

<tex>\mbox{RP} = \{L \mid \exists m: \mbox{P}(m(x) = 1 \mid x \in L)\geq \frac{1}{2}\}</tex>, где <tex>m</tex> - вероятностная машина Тьюринга;

<tex>\mbox{coRP} = \{L \mid \exists m: \mbox{P}(m(x) = 0 \mid x \in notin L)\geq \frac{1}{2}\}</tex>, где  В этих определениях <tex>m</tex> - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.

Поскольку ранее было доказано утверждение о равенстве классов '''ZPP ''' и '''ZPP'''', можно записать утверждение этой теоремы в виде:

Вероятностная машина Алгоритм для вероятностной машины Тьюринга <tex>m_2m</tex> из определения класса '''RP ''' будет работать следующим образомвыглядеть так:

m2 <tex>m</tex>(x) { '''switch ''' (m1<tex>m_1</tex>(x))

case 0: '''return ''' 0; case 1: '''return ''' 1; case ?: '''return ''' 0;''//<tex>m_1</tex> выдала ответ "не знаю"''

}</code>Так как машина <tex>m_1</tex> выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах 0 или 1 никогда не ошибается, вероятность правильного ответа <tex>m</tex> в случае, если слово принадлежит языку, будет не меньше одной второй, а слово не из языка всегда будет обнаружено, что соответствует определению класса '''RP'''. Аналогичным образом доказывается, что <tex>\L \in \mbox{coRP}</tex>: <code> <tex>m</tex>(x){ '''switch''' (<tex>m_1</tex>(x)) { case 0: '''return''' 0; case 1: '''return''' 1; case ?: '''return''' 1; ''//<tex>m_1</tex> выдала ответ "не знаю"'' } }</code>Осталось показать, что <tex> \mbox{RP} \bigcap \mbox{coRP} \subset \mbox{ZPP'} </tex>. То есть если <tex>L \in \mbox{RP} </tex> и <tex>L \in \mbox{coRP} </tex>, то <tex>L \in \mbox{ZPP'} </tex>. Пусть <tex>m_1</tex> - вероятностная машина Тьюринга для языка <tex>L</tex> из определения '''RP''', а <tex>m_2</tex> - соответствующая машина из определения '''coRP'''. Тогда алгоритм для машины <tex>m</tex> из определения '''ZPP'''' будет устроен следующим образом: <code> <tex>m</tex>(x){ '''if''' (<tex>m_2</tex>(x)) '''return''' 1; else '''if''' (!<tex>m_1</tex>(x)) '''return''' 0; return ?; ''//возвращаем ответ "не знаю"'' }