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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Убрано про ZPP, это уже перемещено в новую статью)
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 3 участников)
Строка 2: Строка 2:
 
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
 
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
  
== Основные определения ==
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 23: Строка 22:
  
 
<tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(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{RP}</tex> (от ''randomized polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
 
# <tex>x \notin L \Rightarrow \operatorname{P}(p(x) = 0) = 1</tex>;<br>
 
# <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>
 
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|).</tex>
 
}}
 
<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.
 
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
 
 
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
 
 
{{Определение
 
|definition =
 
<tex>\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}</tex>.
 
}}
 
Класс <tex>\mathrm{coRP}</tex> допускает ошибки программ на словах, не принадлежащих <tex>L</tex>.
 
 
{{Определение
 
|definition =
 
<tex>\mathrm{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
 
# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;
 
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|)</tex>.
 
}}
 
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.
 
 
== Соотношение вероятностных классов ==
 
{{Теорема
 
|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> оказалось больше.
 
}}
 
 
{{Теорема
 
|statement =
 
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
 
|proof =
 
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
 
  <tex>q</tex>(x)
 
    u <- <tex>p</tex>(x)
 
    v <- <tex>p</tex>(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>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
 
 
Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
 
 
}}
 
}}
  
 
== См. также ==
 
== См. также ==
* [[Теоремы о BPP, BPPweak и BPPstrong]]
+
* [[Классы RP и coRP]]
* [[Уменьшение ошибки в классе RP]]
+
* [[Класс ZPP]]
* [[Теорема Лаутемана]]
+
* [[Класс BPP]]
  
 
== Литература ==
 
== Литература ==
 
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]
 
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

Текущая версия на 19:43, 4 сентября 2022

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


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


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


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

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

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

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

[math]R_i \in \Sigma[/math] как зависящие от [math]i[/math] первых битов вероятностной ленты, [math]\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s[/math] — префикс [math]r \in R_i\}|[/math].

[math]R \in \Sigma[/math] как счетное объединение событий, при этом из их дизъюнктности следует, что [math]\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)[/math].
[math]\triangleleft[/math]

См. также

Литература