15
правок
Изменения
Нет описания правки
==Теорема о равенстве ZPP и пересечения RP и coRP==
Воспользуемся следующим определением [[ Класс ZPP | '''ZPP''' ]]: <tex>\mbox{ZPP'} = \mbox{RP}L \mid \exists m : L(m)=L,~ p(m(x) = ?) \bigcaple \mboxfrac{1}{coRP2}\}</tex>, где <tex>m</tex>- это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.
'''Доказательство.'''
<tex>\mbox{ZPP'} \subset\mbox{RP}</tex>
Пусть язык <tex>\L = L(m_1) \in \mbox{ZPP}</tex>. Нужно показать, что <tex>\L \in \mbox{RP}</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> 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''''.
