Изменения

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

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

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

Поскольку ранее было доказано утверждение о равенстве классов <tex>\mbox{ZPP и } = \mbox{RP}\bigcap\mbox{coRP}</tex> Воспользуемся следующим определением [[ Класс ZPP| '''ZPP''' ]]: <tex>\mbox{ZPP} = \{ L \mid \exists m : L(m)=L,~ p(m(x) = ?) \le \frac{1}{2} \}</tex>, можно записать утверждение этой теоремы в виде: где <tex>m</tex> - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа. '''Доказательство'''

<tex>\mbox{ZPP'} = \subset\mbox{RP}\bigcap\mbox{coRP}</tex>

'''ДоказательствоПусть язык <tex> L = L(m_1) \in \mbox{ZPP}</tex>. Нужно показать, что <tex>\L \in \mbox{RP}</tex>.'''

Алгоритм для вероятностной машины Тьюринга <tex>\mbox{ZPP'} \subset\mbox{RP}m</tex>из определения класса '''RP''' будет выглядеть так:

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

Вероятностная машина Тьюринга Аналогичным образом доказывается, что <tex>m_2\L \in \mbox{coRP}</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''' 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_1</tex>(x)) '''return''' 1; '''if''' (!<tex>m_2</tex>(x)) '''return''' 0; '''return''' ?; ''//возвращаем ответ "не знаю"'' }