15
правок
Изменения
Новая страница: «==Определение классов RP и coRP== Классы языков RP и coRP определяются следующим образом: <tex>\mbox{RP}…»
==Определение классов RP и coRP==
Классы языков RP и coRP определяются следующим образом:
<tex>\mbox{RP} = \{L \mid \exists m: \mbox{P}(m(x) = 1 \mid x \in L)\geq \frac{1}{2}\}</tex>, где <tex>m</tex> - вероятностная машина Тьюринга;
<tex>\mbox{coRP} = \{L \mid \exists m: \mbox{P}(m(x) = 0 \mid x \in L)\geq \frac{1}{2}\}</tex>, где <tex>m</tex> - вероятностная машина Тьюринга.
==Теорема о равенстве ZPP и пересечения RP и coRP==
Поскольку ранее было доказано утверждение о равенстве классов ZPP и ZPP', можно записать утверждение этой теоремы в виде:
<tex>\mbox{ZPP'} = \mbox{RP}\bigcap\mbox{coRP}</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_2</tex> из определения класса RP будет работать следующим образом:
<code>
m2(x) {
switch (m1(x))
{
case 0: return 0;
case 1: return 1;
case ?: return 0;
}
}
</code>
Классы языков RP и coRP определяются следующим образом:
<tex>\mbox{RP} = \{L \mid \exists m: \mbox{P}(m(x) = 1 \mid x \in L)\geq \frac{1}{2}\}</tex>, где <tex>m</tex> - вероятностная машина Тьюринга;
<tex>\mbox{coRP} = \{L \mid \exists m: \mbox{P}(m(x) = 0 \mid x \in L)\geq \frac{1}{2}\}</tex>, где <tex>m</tex> - вероятностная машина Тьюринга.
==Теорема о равенстве ZPP и пересечения RP и coRP==
Поскольку ранее было доказано утверждение о равенстве классов ZPP и ZPP', можно записать утверждение этой теоремы в виде:
<tex>\mbox{ZPP'} = \mbox{RP}\bigcap\mbox{coRP}</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_2</tex> из определения класса RP будет работать следующим образом:
<code>
m2(x) {
switch (m1(x))
{
case 0: return 0;
case 1: return 1;
case ?: return 0;
}
}
</code>
