Соотношение вероятностных классов — различия между версиями
Строка 48: | Строка 48: | ||
Достаточно взять <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>. Из сделанного выше замечания следует, что работу функции ''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> будет перебирать все | + | 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> оказалось больше. |
}} | }} | ||
Версия 18:03, 1 июня 2018
Теорема: |
. |
Доказательство: |
Утверждение является очевидным, так как программы, удовлетворяющие ограничениям , также удовлетворяют ограничениям класса .Докажем, что . Для этого, покажем, что . Тогда из будет следовать требуемое.1) . Достаточно вместо возвращать .2) . Достаточно вместо возвращать .3) . Пусть программа удовлетворяет ограничениям и ошибается на словах из языка с вероятностью не более , а программа удовлетворяет ограничениям и ошибается на словах не из языка с аналогичной вероятностью. Построим программу для :Вероятность вывести (x) if (x) = 0 return 0 if (x) = 1 return 1 return ? есть . |
Теорема: |
. |
Доказательство: |
1. . Если в программе для заменить все вызовы random() на недетерминированный выбор, то получим программу для с ограничениями .2. . Приведем программу с ограничениями класса , которая разрешает . Пусть функция infair_coin() моделирует нечестную монету, а именно возвращает единицу с вероятностью , где мы определим позже, и ноль с вероятностью . Пусть также — верификатор сертификатов для . Тогда будет выглядеть следующим образом:(x) c <- случайный сертификат if (x, c) return 1 return infair_coin() Необходимо удовлетворить условию .Пусть . В этом случае вернет и результат работы программы будет зависеть от нечестной монеты. Она вернет с вероятностью .Пусть по формуле полной вероятности , где — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом и существует хотя бы один правильный сертификат, . Найдем из неравенства : . Тогда; ; . Достаточно взять 3. . Из сделанного выше замечания следует, что работу функции infair_coin() можно смоделировать с помощью не более чем вызовов random(). Также учтем, что длина сертификата и время работы полиномиальны относительно . Таким образом, мы построили программу , удовлетворяющую ограничениям класса . . Пусть — программа для языка . Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для будет перебирать все возможные вероятностные ленты нужной полиномиальной длины и запускать на них . Ответом будет или в зависимости от того, каких ответов оказалось больше. |
Теорема: |
. |
Доказательство: |
Пусть — программа для . Программу для определим следующим образом:(x) u <- (x) v <- (x) return u or v Пусть . В этом случае вероятность ошибки равна .Пусть Аналогично доказывается, что . Тогда с вероятностью будет верно и вернет правильный ответ. . |