Сложностные классы 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},~ \mbox{P}(m(x) = 0 \mid x \notin L) = 1\}[/math]

[math]\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\}[/math]

В этих определениях [math]m[/math] - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.

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

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

Воспользуемся следующим определением ZPP :

[math]\mbox{ZPP} = \{ L \mid \exists m : L(m)=L,~ p(m(x) = ?) \le \frac{1}{2} \}[/math],

где [math]m[/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] выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах [math]0[/math] или [math]1[/math] никогда не ошибается, вероятность правильного ответа [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_1[/math](x))
      return 1;
   if (![math]m_2[/math](x))
      return 0;
   return ?; //возвращаем ответ "не знаю"
}

Пусть [math] x \in L [/math]. Тогда вероятность [math]\mbox{P}(m_1(x) = 1) \geq \frac{1}{2}[/math]. Если же [math]m_1[/math] вернула [math]0[/math], то, поскольку всегда [math]m_2(x) = 1[/math] в этой ситуации, машина [math]m[/math] вернет "не знаю". Получается, что [math]\mbox{P}(m(x) = ?) \leq \frac{1}{2}[/math].

Аналогично, если [math] x \notin L [/math], то [math]\mbox{P}(m(x) = 0) = \mbox{P}(m_2(x) = 0) \geq \frac{1}{2}[/math].

В итоге получаем, что машина [math]m[/math] никогда не ошибается и возвращает определенный результат с вероятностью большей либо равной одной второй, что соответствует определению класса ZPP.