322
правки
Изменения
→Соотношение вероятностных классов
|proof =
1. Утверждение <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</tex>.{{Определение|definition =<tex>\mathrm{ZPP}_1</tex> — множество языков <tex>L</tex>, для которых <tex>\exists p, p(x) \in \{0, 1, ?\}, \forall x</tex>:1) <tex>p(x) \ne ? \Rightarrow p(x) = [x \in L]</tex>; 2) <tex>\operatorname{P}(p(x) = ?) \le 1/2</tex>; 3) <tex>\operatorname{T}(p(x)) \le poly(|x|).</tex>}}Сначала докажем, что <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex>. 1) <tex>\mathrm{ZPP} \subset \mathrm{ZPP}_1</tex>. ... 2) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>. ... Теперь покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>. 1) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?<br/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</tex> ошибается на словах из языка с вероятностью не более <tex>1/2</tex>, <tex>q</tex> ошибается на словах не из языка с аналогичной вероятностью. Вычислим значения <tex>p(x)</tex> и <tex>q(x)</tex>. Вернем <tex>0</tex>, если <tex>p(x) = 0</tex>. Вернем <tex>1</tex>, если <tex>q(x) = 1</tex>. В противном случае вернем <tex>?</tex>. Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p(x) = 1, q(x) = 0) \le 1/2</tex>.
2. Покажем, что <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в разрешающей программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу с ограничениями <tex>\mathrm{NP}</tex>, разрешающую <tex>L</tex>.
Покажем, что <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{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>\mathrm{PP}</tex>, которая разрешает <tex>L \in \mathrm{NP}</tex>. Пусть функция ''infair_coin''() моделирует нечестную монету, а именно возвращает единицу с вероятностью <tex>1/2 - \varepsilon</tex>, где <tex>\varepsilon</tex> мы определим позже, и ноль с вероятностью <tex>1/2 + \varepsilon</tex>. Пусть также <tex>V</tex> — верификатор сертификатов для <tex>L</tex>. Тогда <tex>q</tex> будет выглядеть следующим образом:
q(x):
