Сложностные классы 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]\mbox{coRP} = \{L \mid \exists m: \mbox{P}(m(x) = 0 \mid x \notin 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[/math] из определения класса RP будет выглядеть так:

[math]m[/math](x){
   switch ([math]m_1[/math](x))
   {
    case 0: return 0;
    case 1: return 1;
    case ?: return 0; //[math]m_1[/math] выдала ответ "не знаю"
   }
}

Так как машина [math]m_1[/math] выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах 0 или 1 никогда не ошибается, вероятность правильного ответа [math]m[/math] в случае, если слово принадлежит языку, будет не меньше одной второй, а слово не из языка всегда будет обнаружено, что соответствует определению класса RP.

Аналогичным образом доказывается, что [math]\L \in \mbox{coRP}[/math]:

[math]m[/math](x){
   switch ([math]m_1[/math](x))
   {
    case 0: return 0;
    case 1: return 1;
    case ?: return 1; //[math]m_1[/math] выдала ответ "не знаю"
   }
}

Осталось показать, что [math] \mbox{RP} \bigcap \mbox{coRP} \subset \mbox{ZPP'} [/math]. То есть если [math]L \in \mbox{RP} [/math] и [math]L \in \mbox{coRP} [/math], то [math]L \in \mbox{ZPP'} [/math].

Пусть [math]m_1[/math] - вероятностная машина Тьюринга для языка [math]L[/math] из определения RP, а [math]m_2[/math] - соответствующая машина из определения coRP. Тогда алгоритм для машины [math]m[/math] из определения ZPP' будет устроен следующим образом:

[math]m[/math](x){
   if ([math]m_2[/math](x))
      return 1;
   else
      if (![math]m_1[/math](x))
         return 0;
   return ?; //возвращаем ответ "не знаю"
}