Материал из Викиконспекты
| Теорема: |
[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] |
Литература
