Сложностные классы RP и coRP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 3 участников)
Строка 2: Строка 2:
 
Классы языков '''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>\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}\}</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> - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.
+
В этих определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа.
  
 
==Теорема о равенстве ZPP и пересечения RP и coRP==
 
==Теорема о равенстве ZPP и пересечения RP и coRP==
Поскольку ранее было доказано утверждение о равенстве классов '''ZPP''' и '''ZPP'''', можно записать утверждение этой теоремы в виде:
+
<tex>\mbox{ZPP} = \mbox{RP}\bigcap\mbox{coRP}</tex>
  
<tex>\mbox{ZPP'} = \mbox{RP}\bigcap\mbox{coRP}</tex>
+
Воспользуемся следующим определением [[ Класс ZPP | '''ZPP''' ]]:
  
'''Доказательство.'''
+
<tex>\mbox{ZPP} = \{ L \mid \exists m : L(m)=L,~ p(m(x) = ?) \le \frac{1}{2} \}</tex>,
  
<tex>\mbox{ZPP'} \subset\mbox{RP}</tex>
+
где <tex>m</tex> - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.
  
Пусть язык <tex>\L = L(m_1) \in \mbox{ZPP}</tex>. Нужно показать, что <tex>\L \in \mbox{RP}</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''' будет выглядеть так:
 
Алгоритм для вероятностной машины Тьюринга <tex>m</tex> из определения класса '''RP''' будет выглядеть так:
Строка 31: Строка 35:
 
  }
 
  }
 
</code>
 
</code>
Так как машина <tex>m_1</tex> выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах 0 или 1 никогда не ошибается, вероятность правильного ответа <tex>m</tex> в случае, если слово принадлежит языку, будет не меньше одной второй, а слово не из языка всегда будет обнаружено, что соответствует определению класса '''RP'''.
+
Так как машина <tex>m_1</tex> выдает ответ "не знаю" с вероятностью не больше одной второй, а в ответах <tex>0</tex> или <tex>1</tex> никогда не ошибается, вероятность правильного ответа <tex>m</tex> в случае, если слово принадлежит языку, будет не меньше одной второй, а слово не из языка всегда будет обнаружено, что соответствует определению класса '''RP'''.
  
 
Аналогичным образом доказывается, что <tex>\L \in \mbox{coRP}</tex>:
 
Аналогичным образом доказывается, что <tex>\L \in \mbox{coRP}</tex>:
Строка 45: Строка 49:
 
  }
 
  }
 
</code>
 
</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> \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'''' будет устроен следующим образом:
+
Пусть <tex>m_1</tex> - вероятностная машина Тьюринга для языка <tex>L</tex> из определения '''RP''', а <tex>m_2</tex> - соответствующая машина из определения '''coRP'''. Тогда алгоритм для машины <tex>m</tex> из определения '''ZPP''' будет устроен следующим образом:
  
 
<code>
 
<code>
 
  <tex>m</tex>(x){
 
  <tex>m</tex>(x){
     '''if''' (<tex>m_2</tex>(x))
+
     '''if''' (<tex>m_1</tex>(x))
 
       '''return''' 1;
 
       '''return''' 1;
     else
+
     '''if''' (!<tex>m_2</tex>(x))
      '''if''' (!<tex>m_1</tex>(x))
+
      '''return''' 0;
          '''return''' 0;
+
     '''return''' ?; ''//возвращаем ответ "не знаю"''
     return ?; ''//возвращаем ответ "не знаю"''
 
 
  }
 
  }
 
</code>
 
</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'''.

Текущая версия на 19:22, 4 сентября 2022

Определение классов 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.