Изменения

'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ , говоря неформально, к случайным битамгенератору случайных чисел. Мы рассмотрим классы сложности, для которых разрешающие программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.

'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).

'''Вероятностная машина Тьюринга''' (ВМТ) — обобщение детерминированной машины детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.

Введем [http://ru.wikipedia.org/wiki/Вероятностное_пространство вероятностное пространство ] <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Будем считать, что <tex>\Sigma</tex> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.

|statement= Пусть <tex>m</tex> — ВМТ. Тогда для любых <tex>x</tex> и <tex>\forall A</tex> — предикат предиката от ВМТ: <tex>m</tex> выполняется <tex>R = \{r \bigm| A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.

Считаем<tex>R = \bigcup\limits_{i = 0}^\infty R_i</tex>, что где <tex>R_i = \{r \bigm| A(m(x, r)), m</tex> фиксированпрочитала ровно <tex>i</tex> первых символов с <tex>r\}</tex>. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения <tex>R_i</tex> следует, что они дизъюнктны.

<tex>R = R_i \bigcupin \limits_{Sigma</tex> как зависящие от <tex>i = 0}^\infty R_i</tex>первых битов вероятностной ленты, <tex>\operatorname{P}(R_i ) = \frac{r 1}{2^i} \cdot |\{s \bigm| |s| A(m(x= i, r)), ms</tex> прочитала ровно <tex>i</tex> первых символов с вероятностной ленты— префикс <tex>r \in R_i\}|</tex>.

<tex>R_i \in \Sigma</tex>, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s : |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>. <tex>R \in \Sigma</tex> как счетное объединение множествсобытий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.}} == Вероятностные сложностные классы =={{Определение|definition =<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:1) <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>2) <tex>\operatorname{E}(\operatorname{T}(p(x))) = poly(|x|)</tex>.<br>}} {{Определение|definition =<tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:1) <tex>x \notin L \Rightarrow p(x) = 0</tex>;<br>2) <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>3) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>}}Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы. Определим также <tex>\mathrm{coRP}</tex> как дополнение к <tex>\mathrm{RP}</tex>. <tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>. {{Определение|definition =<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:1) <tex>\operatorname{P}(p(x) = [x \in L]) \ge 2/3</tex>;<br>2) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|)</tex>.}}Аналогично сделанному выше замечанию, константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>. Замена константы на <tex>1/2</tex> сделало бы данный класс равным <tex>\Sigma^*</tex>. {{Определение|definition =<tex>\mathrm{PP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:1) <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;<br>2) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|)</tex>.}} == Соотношение вероятностных классов =={{Теорема|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</tex>.{{Определение|definition =<tex>\mathrm{ZPP}_1</tex> — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:1) <tex>p(x) \in \{0, 1, ?\}</tex>; 2) <tex>p(x) \ne ? \Rightarrow p(x) = [x \in L]</tex>; 3) <tex>\operatorname{P}(p(x) = ?) \le 1/2</tex>; 4) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>}}Сначала докажем, что <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex>. 1) <tex>\mathrm{ZPP} \subset \mathrm{ZPP}_1</tex>. Пусть <tex>X</tex> — случайная величина, равная времени работы программы <tex>p</tex> для <tex>\mathrm{ZPP}</tex>, <tex>X > 0</tex>. Запишем [http://ru.wikipedia.org/wiki/Неравенство_Маркова неравенство Маркова]: <tex>\operatorname{P}(X > k \operatorname{E}[X]) \le 1/k</tex>. Подставляем <tex>k = 2</tex>. Тогда, если запустить программу <tex>p</tex> для <tex>ZPP</tex> с ограничением по времени <tex>2E[X]</tex>, она не успеет завершиться с вероятностью, не превышающей <tex>1/2</tex>. В этом случае программа <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex> вернет <tex>?</tex>, а иначе — результат программы <tex>p</tex>. Заметим, что <tex>q</tex> работает полиномиальное время, так как <tex>E[X]</tex> ограничено некоторым полиномом по определению класса <tex>\mathrm{ZPP}</tex>. 2) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>. Будем запускать программу p для <tex>\mathrm{ZPP_1}</tex>, пока не получим ответ, отличный от <tex>?</tex>. Математическое ожидание количества запусков <tex>p</tex> не превышает <tex>\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2</tex>. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса <tex>\mathrm{ZPP}</tex>. Теперь покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</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</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>. }} {{Теорема|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.|proof = Покажем, что <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): c <- случайный сертификат (полиномиальной длины) '''return''' V(x, c) ? 1 : infair_coin()Необходимо удовлетворить условию <tex>\operatorname{P}(p(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}(p(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку все сертификаты имеют полиномиальную длину и существует хотя бы один правильный сертификат, <tex>p_0</tex> не более чем экспоненциально мала. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(p(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 < p_0 (1 - p_0) / 2</tex>. Достаточно взять <tex>\varepsilon < p_0 / 4</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью полиномиального количества вызовов ''random''(). Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.}} {{Теорема|statement =1. <tex>\mathrm{RP} \subset \mathrm{BPP}</tex>;<br>2. <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.|proof =Пусть <tex>p</tex> — программа для <tex>L \in RP</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом: q(x): u <- p(x) v <- p(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>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ. Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.

* [[Теоремы о BPP, BPPweak Классы RP и BPPstrongcoRP]]* [[Уменьшение ошибки в классе RPКласс ZPP]]* [[Теорема ЛаутеманаКласс BPP]]