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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>. |proof = 1. <tex>\mathrm{RP} \subset \mathrm{NP}...»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 4 участников)
Строка 1: Строка 1:
 +
{{Теорема
 +
|statement = <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
 +
|proof =
 +
Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, удовлетворяющие ограничениям <tex>\mathrm{P}</tex>, также удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.
 +
 +
Докажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
 +
Для этого, покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>. Тогда из <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex> будет следовать требуемое.
 +
 +
1) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>0</tex>.
 +
 +
2) <tex>\mathrm{ZPP}_1 \subset\mathrm{coRP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>1</tex>.
 +
 +
3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.
 +
Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:
 +
  <tex>q</tex>(x)
 +
    '''if''' <tex>p_2</tex>(x) = 0
 +
      '''return''' 0
 +
    '''if''' <tex>p_1</tex>(x) = 1
 +
      '''return''' 1
 +
    '''return''' ?
 +
 +
Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2</tex>.
 +
}}
 +
 
{{Теорема
 
{{Теорема
 
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
 
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
Строка 9: Строка 33:
 
     '''if''' <tex>V</tex>(x, c)
 
     '''if''' <tex>V</tex>(x, c)
 
       '''return''' 1
 
       '''return''' 1
     '''return''' infair_coin()
+
     '''return''' unfair_coin()
 
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.
 
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.
  
Строка 22: Строка 46:
 
<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.
 
<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.
  
Достаточно взять <tex>\varepsilon \le p_0 / 2</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью не более чем <tex>s(n) + 1</tex> вызовов ''random''(). Также учтем, что длина сертификата и время работы <tex>V</tex> полиномиальны относительно <tex>|x|</tex>. Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.
+
Достаточно взять <tex>\varepsilon \le p_0 / 2</tex>. Из сделанного выше замечания следует, что работу функции ''unfair_coin''() можно смоделировать с помощью не более чем <tex>s(n) + 1</tex> вызовов ''random''(). Также учтем, что длина сертификата и время работы <tex>V</tex> полиномиальны относительно <tex>|x|</tex>. Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.
 +
 
 +
3. <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все возможные вероятностные ленты нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
 +
}}
 +
 
 +
{{Теорема
 +
|statement =
 +
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
 +
|proof =
 +
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
 +
  <tex>q</tex>(x)
 +
    u <- <tex>p</tex>(x)
 +
    v <- <tex>p</tex>(x)
 +
    '''return''' u '''or''' v
 +
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.
 +
 
 +
Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
  
3. <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
+
Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
 
}}
 
}}
  
 
== Литература ==
 
== Литература ==
 
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]
 
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

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

Теорема:
[math]\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math].
Доказательство:
[math]\triangleright[/math]

Утверждение [math]\mathrm{P} \subset \mathrm{ZPP}[/math] является очевидным, так как программы, удовлетворяющие ограничениям [math]\mathrm{P}[/math], также удовлетворяют ограничениям класса [math]\mathrm{ZPP}[/math].

Докажем, что [math]\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math]. Для этого, покажем, что [math]\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}[/math]. Тогда из [math]\mathrm{ZPP} = \mathrm{ZPP}_1[/math] будет следовать требуемое.

1) [math]\mathrm{ZPP}_1 \subset \mathrm{RP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]0[/math].

2) [math]\mathrm{ZPP}_1 \subset\mathrm{coRP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]1[/math].

3) [math]\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}[/math]. Пусть программа [math]p_1[/math] удовлетворяет ограничениям [math]\mathrm{RP}[/math] и ошибается на словах из языка [math]L[/math] с вероятностью не более [math]1/2[/math], а программа [math]p_2[/math] удовлетворяет ограничениям [math]\mathrm{coRP}[/math] и ошибается на словах не из языка [math]L[/math] с аналогичной вероятностью. Построим программу [math]q[/math] для [math]\mathrm{ZPP}_1[/math]:

 [math]q[/math](x)
   if [math]p_2[/math](x) = 0
     return 0
   if [math]p_1[/math](x) = 1
     return 1
   return ?
Вероятность вывести [math]?[/math] есть [math]\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2[/math].
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}[/math].
Доказательство:
[math]\triangleright[/math]

1. [math]\mathrm{RP} \subset \mathrm{NP}[/math]. Если в программе для [math]L \in \mathrm{RP}[/math] заменить все вызовы random() на недетерминированный выбор, то получим программу для [math]L[/math] с ограничениями [math]\mathrm{NP}[/math].

2. [math]\mathrm{NP} \subset \mathrm{PP}[/math]. Приведем программу [math]q[/math] с ограничениями класса [math]\mathrm{PP}[/math], которая разрешает [math]L \in \mathrm{NP}[/math]. Пусть функция infair_coin() моделирует нечестную монету, а именно возвращает единицу с вероятностью [math]1/2 - \varepsilon[/math], где [math]\varepsilon[/math] мы определим позже, и ноль с вероятностью [math]1/2 + \varepsilon[/math]. Пусть также [math]V[/math] — верификатор сертификатов для [math]L[/math]. Тогда [math]q[/math] будет выглядеть следующим образом:

 [math]q[/math](x)
   c <- случайный сертификат
   if [math]V[/math](x, c)
     return 1
   return unfair_coin()

Необходимо удовлетворить условию [math]\operatorname{P}(q(x) = [x \in L]) \gt 1/2[/math].

Пусть [math]x \notin L[/math]. В этом случае [math]V(x, c)[/math] вернет [math]0[/math] и результат работы программы будет зависеть от нечестной монеты. Она вернет [math]0[/math] с вероятностью [math]1/2 + \varepsilon \gt 1/2[/math].

Пусть [math]x \in L[/math]. Тогда по формуле полной вероятности [math]\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)[/math], где [math]p_0[/math] — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом [math]s(n), n = |x|[/math] и существует хотя бы один правильный сертификат, [math]p_0 \ge 2^{-s(n)}[/math]. Найдем [math]\varepsilon[/math] из неравенства [math]\operatorname{P}(q(x) = 1) \gt 1/2[/math]:

[math]p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon \gt 1/2[/math];

[math]p_0 / 2 + (p_0 - 1)\varepsilon \gt 0[/math];

[math]\varepsilon \lt \frac{p_0}{2 (1 - p_0)}[/math].

Достаточно взять [math]\varepsilon \le p_0 / 2[/math]. Из сделанного выше замечания следует, что работу функции unfair_coin() можно смоделировать с помощью не более чем [math]s(n) + 1[/math] вызовов random(). Также учтем, что длина сертификата и время работы [math]V[/math] полиномиальны относительно [math]|x|[/math]. Таким образом, мы построили программу [math]q[/math], удовлетворяющую ограничениям класса [math]\mathrm{PP}[/math].

3. [math]\mathrm{PP} \subset \mathrm{PS}[/math]. Пусть [math]p[/math] — программа для языка [math]L \in \mathrm{PP}[/math]. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для [math]\mathrm{PS}[/math] будет перебирать все возможные вероятностные ленты нужной полиномиальной длины и запускать на них [math]p[/math]. Ответом будет [math]0[/math] или [math]1[/math] в зависимости от того, каких ответов [math]p[/math] оказалось больше.
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]p[/math] — программа для [math]L \in \mathrm{RP}[/math]. Программу [math]q[/math] для [math]\mathrm{BPP}[/math] определим следующим образом:

 [math]q[/math](x)
   u <- [math]p[/math](x)
   v <- [math]p[/math](x)
   return u or v

Пусть [math]x \in L[/math]. В этом случае вероятность ошибки равна [math]\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4[/math].

Пусть [math]x \notin L[/math]. Тогда с вероятностью [math]1[/math] будет верно [math]u = 0, v = 0[/math] и [math]q[/math] вернет правильный ответ.

Аналогично доказывается, что [math]\mathrm{coRP} \subset \mathrm{BPP}[/math].
[math]\triangleleft[/math]

Литература