Вероятностные вычисления. Вероятностная машина Тьюринга

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

Основные определения

Определение:

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

Определение:

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

Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции random(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. $p(x) = p(x, r)$, где $r$ — вероятностная лента.

Введем вероятностное пространство $(\Omega, \Sigma, \operatorname{P})$, где пространство элементарных исходов $\Omega$ — множество всех вероятностных лент, $\Sigma$ — сигма-алгебра подмножеств $\Omega$, $\operatorname{P}$ — вероятностная мера, заданная на $\Sigma$. Будем считать, что $\Sigma$ порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.

Теорема:

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

Доказательство:

$\triangleright$

$R = \bigcup\limits_{i = 0}^\infty R_i$, где $R_i = \{r \bigm| A(m(x, r)), m$ прочитала ровно $i$ первых символов с $r\}$. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения $R_i$ следует, что они дизъюнктны. $R_i \in \Sigma$ как зависящие от $i$ первых битов вероятностной ленты, $\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s$ — префикс $r \in R_i\}|$. $R \in \Sigma$ как счетное объединение событий, при этом из их дизъюнктности следует, что $\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)$.

$\triangleleft$

Вероятностные классы сложности

Определение:

$\mathrm{PP}$ (от probabilistic polynomial) — множество языков $L$, для которых $\exists p \forall x$: $\operatorname{P}(p(x) = [x \in L]) \gt 1/2$; $\forall r \operatorname{T}(p, x) \le poly(|x|)$.

$\mathrm{PP}$ также допускает двусторонние ошибки, но является более широким по сравнению с $\mathrm{BPP}$.

Соотношение вероятностных классов

Теорема:

$\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}$.

Доказательство:

$\triangleright$

1. $\mathrm{RP} \subset \mathrm{NP}$. Если в программе для $L \in \mathrm{RP}$ заменить все вызовы random() на недетерминированный выбор, то получим программу для $L$ с ограничениями $\mathrm{NP}$. 2. $\mathrm{NP} \subset \mathrm{PP}$. Приведем программу $q$ с ограничениями класса $\mathrm{PP}$, которая разрешает $L \in \mathrm{NP}$. Пусть функция infair_coin() моделирует нечестную монету, а именно возвращает единицу с вероятностью $1/2 - \varepsilon$, где $\varepsilon$ мы определим позже, и ноль с вероятностью $1/2 + \varepsilon$. Пусть также $V$ — верификатор сертификатов для $L$. Тогда $q$ будет выглядеть следующим образом: $q$(x) c <- случайный сертификат if $V$(x, c) return 1 return infair_coin() Необходимо удовлетворить условию $\operatorname{P}(q(x) = [x \in L]) \gt 1/2$. Пусть $x \notin L$. В этом случае $V(x, c)$ вернет $0$ и результат работы программы будет зависеть от нечестной монеты. Она вернет $0$ с вероятностью $1/2 + \varepsilon \gt 1/2$. Пусть $x \in L$. Тогда по формуле полной вероятности $\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)$, где $p_0$ — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом $s(n), n = |x|$ и существует хотя бы один правильный сертификат, $p_0 \ge 2^{-s(n)}$. Найдем $\varepsilon$ из неравенства $\operatorname{P}(q(x) = 1) \gt 1/2$: $p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon \gt 1/2$; $p_0 / 2 + (p_0 - 1)\varepsilon \gt 0$; $\varepsilon \lt \frac{p_0}{2 (1 - p_0)}$. Достаточно взять $\varepsilon \le p_0 / 2$. Из сделанного выше замечания следует, что работу функции infair_coin() можно смоделировать с помощью не более чем $s(n) + 1$ вызовов random(). Также учтем, что длина сертификата и время работы $V$ полиномиальны относительно $|x|$. Таким образом, мы построили программу $q$, удовлетворяющую ограничениям класса $\mathrm{PP}$. 3. $\mathrm{PP} \subset \mathrm{PS}$. Пусть $p$ — программа для языка $L \in \mathrm{PP}$. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для $\mathrm{PS}$ будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них $p$. Ответом будет $0$ или $1$ в зависимости от того, каких ответов $p$ оказалось больше.

$\triangleleft$

См. также

• Класс BPP
• Классы RP и coRP
• Теорема Лаутемана

Литература

• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach