1632
правки
Изменения
м
rollbackEdits.php mass rollback
где <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>.
Алгоритм для вероятностной машины Тьюринга <tex>m</tex> из определения класса '''RP''' будет выглядеть так:
