Сложностные классы RP и coRP

Определение классов RP и coRP

Классы языков RP и coRP определяются следующим образом:

[math]\mbox{RP} = \{L \mid \exists m: \mbox{P}(m(x) = 1 \mid x \in L)\geq \frac{1}{2}\}[/math], где [math]m[/math] - вероятностная машина Тьюринга;

[math]\mbox{coRP} = \{L \mid \exists m: \mbox{P}(m(x) = 0 \mid x \in L)\geq \frac{1}{2}\}[/math], где [math]m[/math] - вероятностная машина Тьюринга.

Теорема о равенстве ZPP и пересечения RP и coRP

Поскольку ранее было доказано утверждение о равенстве классов ZPP и ZPP', можно записать утверждение этой теоремы в виде:

[math]\mbox{ZPP'} = \mbox{RP}\bigcap\mbox{coRP}[/math]

Доказательство.

[math]\mbox{ZPP'} \subset\mbox{RP}[/math]

Пусть язык [math]\L = L(m_1) \in \mbox{ZPP}[/math]. Нужно показать, что [math]\L \in \mbox{RP}[/math].

Вероятностная машина Тьюринга [math]m_2[/math] из определения класса RP будет работать следующим образом:

m2(x) {

   switch (m1(x))
   {
    case 0: return 0;
    case 1: return 1;
    case ?: return 0;
   }

}