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