1632
правки
Изменения
м
Поскольку ранее было доказано утверждение о равенстве классов '''<tex>\mbox{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>,
else '''if''' (!<tex>m_1m_2</tex>(x)) '''return''' 0; '''return ''' ?; ''//возвращаем ответ "не знаю"''
rollbackEdits.php mass rollback
Классы языков '''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==
где <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>m_1</tex> выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах <tex>0 </tex> или <tex>1 </tex> никогда не ошибается, вероятность правильного ответа <tex>m</tex> в случае, если слово принадлежит языку, будет не меньше одной второй, а слово не из языка всегда будет обнаружено, что соответствует определению класса '''RP'''.
Аналогичным образом доказывается, что <tex>\L \in \mbox{coRP}</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_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'''.
