Изменения
Нет описания правки
Классы языков '''RP''' и '''coRP''' определяются следующим образом:
<tex>\mbox{RP} = \{L \mid \exists m: \mbox{P}(m(x) = 1 \mid x \in L)\geq \frac{1}{2},~ \mbox{P}(m(x) = 0 \mid x \notin L) = 1\}</tex>
<tex>\mbox{coRP} = \{L \mid \exists m: \mbox{P}(m(x) = 0 \mid x \notin L)\geq \frac{1}{2},~ \mbox{P}(m(x) = 1 \mid x \in L) = 1\}</tex>
В этих определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа.
==Теорема о равенстве ZPP и пересечения RP и coRP==
Поскольку ранее было доказано утверждение о равенстве показано [[Сложностный класс ZPP, Два эквивалентных определения | равенство классов '''ZPP''' и '''ZPP'''']], можно записать утверждение этой теоремы в виде:
<tex>\mbox{ZPP'} = \mbox{RP}\bigcap\mbox{coRP}</tex>
}
</code>
Так как машина <tex>m_1</tex> выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах <tex>0 </tex> или <tex>1 </tex> никогда не ошибается, вероятность правильного ответа <tex>m</tex> в случае, если слово принадлежит языку, будет не меньше одной второй, а слово не из языка всегда будет обнаружено, что соответствует определению класса '''RP'''.
Аналогичным образом доказывается, что <tex>\L \in \mbox{coRP}</tex>:
<code>
<tex>m</tex>(x){
'''if''' (<tex>m_2m_1</tex>(x))
'''return''' 1;
}
</code>
Пусть <tex> x \in L </tex>. Тогда вероятность <tex>\mbox{P}(m_1(x) = 1) \geq \frac{1}{2}</tex>. Если же <tex>m_1</tex> вернула <tex>0</tex>, то, поскольку всегда <tex>m_2(x) = 1</tex> в этой ситуации, машина <tex>m</tex> вернет "не знаю". Получается, что <tex>\mbox{P}(m(x) = ?) \leq \frac{1}{2}</tex>.
Аналогично, если <tex> x \notin L </tex>, то <tex>\mbox{P}(m(x) = 0) = \mbox{P}(m_2(x) = 0) \geq \frac{1}{2}</tex>.
В итоге получаем, что машина <tex>m</tex> никогда не ошибается и возвращает определенный результат с вероятностью большей либо равной одной второй, что соответствует определению класса '''ZPP''''.
