322
правки
Изменения
Новая страница: «{{Теорема |statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>. |proof = 1. <tex>\mathrm{RP} \subset \mathrm{NP}...»
{{Теорема
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
1. <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу для <tex>L</tex> с ограничениями <tex>\mathrm{NP}</tex>.
2. <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> будет выглядеть следующим образом:
<tex>q</tex>(x)
c <- случайный сертификат
'''if''' <tex>V</tex>(x, c)
'''return''' 1
'''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.
Пусть <tex>x \notin L</tex>. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монеты. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2</tex>.
Пусть <tex>x \in L</tex>. Тогда [[Формула полной вероятности|по формуле полной вероятности]] <tex>\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом <tex>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(q(x) = 1) > 1/2</tex>:
<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;
<tex>p_0 / 2 + (p_0 - 1)\varepsilon > 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>.
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> оказалось больше.
}}
== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
1. <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу для <tex>L</tex> с ограничениями <tex>\mathrm{NP}</tex>.
2. <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> будет выглядеть следующим образом:
<tex>q</tex>(x)
c <- случайный сертификат
'''if''' <tex>V</tex>(x, c)
'''return''' 1
'''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.
Пусть <tex>x \notin L</tex>. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монеты. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2</tex>.
Пусть <tex>x \in L</tex>. Тогда [[Формула полной вероятности|по формуле полной вероятности]] <tex>\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом <tex>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(q(x) = 1) > 1/2</tex>:
<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;
<tex>p_0 / 2 + (p_0 - 1)\varepsilon > 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>.
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> оказалось больше.
}}
== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]
