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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 129: Строка 129:
 
       '''return''' 1
 
       '''return''' 1
 
     '''return''' infair_coin()
 
     '''return''' infair_coin()
−
Необходимо удовлетворить условию <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>.
+
Необходимо удовлетворить условию <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 \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>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(p(x) = 1) > 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 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;

Версия 15:18, 3 июня 2012

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

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

Определение:
Вероятностная лента — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения [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]

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

Определение:
[math]\mathrm{ZPP}[/math] (от zero-error probabilistic polynomial) — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
  1. [math]\operatorname{P}(p(x) \ne [x \in L]) = 0[/math];
  2. [math]\operatorname{E}[\operatorname{T}(p(x))] = poly(|x|)[/math].

[math]\mathrm{ZPP}[/math] — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.

Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу [math]x[/math].


Определение:
[math]\mathrm{RP}[/math] (от randomized polynomial) — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
  1. [math]x \notin L \Rightarrow \operatorname{P}(p(x) = 0) = 1[/math];
  2. [math]x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2[/math];
  3. [math]\forall r \operatorname{T}(p(x)) \le poly(|x|).[/math]

[math]\mathrm{RP}[/math] — сложностный класс, допускающий ошибки программ на словах из [math]L[/math]. Заметим, что константа [math]1/2[/math] в пункте 2 определения [math]\mathrm{RP}[/math] может быть заменена на любую другую из промежутка [math](0, 1)[/math], поскольку требуемой вероятности можно добиться множественным запуском программы.

[math]\mathrm{RP}[/math] можно рассматривать как вероятностный аналог класса [math]\mathrm{NP}[/math], предполагая, что вероятность угадать сертификат в случае его существования не менее [math]1/2[/math].


Определение:
[math]\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}[/math].

Класс [math]\mathrm{coRP}[/math] допускает ошибки программ на словах, не принадлежащих [math]L[/math].


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

[math]\mathrm{BPP}[/math] — сложностный класс, допускающий двусторонние ошибки. Аналогично сделанному выше замечанию, константу [math]2/3[/math] можно заменить на любое число из промежутка [math](1/2, 1)[/math]. Замена константы на [math]1/2[/math] сделало бы данный класс равным [math]\Sigma^*[/math] (программа, возвращающая результат функции random(), подошла бы для любого языка).


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

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

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

Теорема:
[math]\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math].
Доказательство:
[math]\triangleright[/math]

Утверждение [math]\mathrm{P} \subset \mathrm{ZPP}[/math] является очевидным, так как программы, удовлетворяющие ограничениям [math]\mathrm{P}[/math], также удовлетворяют ограничениям класса [math]\mathrm{ZPP}[/math].

Покажем, что [math]\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math]. Для этого определим вспомогательный класс [math]\mathrm{ZPP}_1[/math].

Определение:
[math]\mathrm{ZPP}_1[/math] — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
  1. [math]p(x) \in \{0, 1, ?\}[/math];
  2. [math]p(x) \ne \enskip? \Rightarrow p(x) = [x \in L][/math];
  3. [math]\operatorname{P}(p(x) = \enskip?) \le 1/2[/math];
  4. [math]\forall r \operatorname{T}(p(x)) \le poly(|x|).[/math]

1. Сначала докажем, что [math]\mathrm{ZPP} = \mathrm{ZPP}_1[/math].

1) [math]\mathrm{ZPP} \subset \mathrm{ZPP}_1[/math].

Пусть [math]X[/math] — случайная величина, равная времени работы программы [math]p[/math] для [math]\mathrm{ZPP}[/math], [math]X \gt 0[/math]. Запишем неравенство Маркова:

[math]\operatorname{P}(X \gt k \operatorname{E}[X]) \le 1/k[/math].

Подставим [math]k = 2[/math]. Тогда, если запустить программу [math]p[/math] для [math]\mathrm{ZPP}[/math] с ограничением по времени [math]2E[X][/math], она не успеет завершиться с вероятностью, не превышающей [math]1/2[/math]. Опишем программу [math]q[/math] для [math]\mathrm{ZPP}_1[/math]. Она будет возвращать [math]?[/math], если [math]p[/math] не успеет завершиться, а иначе — результат работы программы [math]p[/math]. Заметим, что [math]q[/math] работает полиномиальное время, так как [math]E[X][/math] ограничено некоторым полиномом по определению класса [math]\mathrm{ZPP}[/math].

2) [math]\mathrm{ZPP_1} \subset \mathrm{ZPP}[/math]. Будем запускать программу [math]p[/math] для [math]\mathrm{ZPP_1}[/math], пока не получим ответ, отличный от [math]?[/math]. Математическое ожидание количества запусков [math]p[/math] не превышает [math]\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2[/math]. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса [math]\mathrm{ZPP}[/math].

2. Теперь покажем, что [math]\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}[/math].

1) [math]\mathrm{ZPP}_1 \subset \mathrm{RP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]0[/math].

2) [math]\mathrm{ZPP}_1 \subset\mathrm{coRP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]1[/math].

3) [math]\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}[/math]. Пусть программа [math]p_1[/math] удовлетворяет ограничениям [math]\mathrm{RP}[/math] и ошибается на словах из языка [math]L[/math] с вероятностью не более [math]1/2[/math], а программа [math]p_2[/math] удовлетворяет ограничениям [math]\mathrm{coRP}[/math] и ошибается на словах не из языка [math]L[/math] с аналогичной вероятностью. Построим программу [math]q[/math] для [math]\mathrm{ZPP}_1[/math]: 

 q(x)
   if [math]p_2[/math](x) = 0
     return 0
   if [math]p_1[/math](x) = 1
     return 1
   return ?
Вероятность вывести [math]?[/math] есть [math]\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2[/math].
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}[/math].
Доказательство:
[math]\triangleright[/math]

1. [math]\mathrm{RP} \subset \mathrm{NP}[/math]. Если в программе для [math]L \in \mathrm{RP}[/math] заменить все вызовы random() на недетерминированный выбор, то получим программу для [math]L[/math] с ограничениями [math]\mathrm{NP}[/math].

2. [math]\mathrm{NP} \subset \mathrm{PP}[/math]. Приведем программу [math]q[/math] с ограничениями класса [math]\mathrm{PP}[/math], которая разрешает [math]L \in \mathrm{NP}[/math]. Пусть функция infair_coin() моделирует нечестную монету, а именно возвращает единицу с вероятностью [math]1/2 - \varepsilon[/math], где [math]\varepsilon[/math] мы определим позже, и ноль с вероятностью [math]1/2 + \varepsilon[/math]. Пусть также [math]V[/math] — верификатор сертификатов для [math]L[/math]. Тогда [math]q[/math] будет выглядеть следующим образом: 

 q(x)
   c <- случайный сертификат (полиномиальной длины)
   if V(x, c)
     return 1
   return infair_coin()

Необходимо удовлетворить условию [math]\operatorname{P}(q(x) = [x \in L]) \gt 1/2[/math].

Пусть [math]x \notin L[/math]. В этом случае [math]V(x, c)[/math] вернет [math]0[/math] и результат работы программы будет зависеть от нечестной монеты. Она вернет [math]0[/math] с вероятностью [math]1/2 + \varepsilon \gt 1/2[/math].

Пусть [math]x \in L[/math]. Тогда по формуле полной вероятности [math]\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)[/math], где [math]p_0[/math] — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом [math]s(n), n = |x|[/math] и существует хотя бы один правильный сертификат, [math]p_0 \ge 2^{-s(n)}[/math]. Найдем [math]\varepsilon[/math] из неравенства [math]\operatorname{P}(q(x) = 1) \gt 1/2[/math]:

[math]p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon \gt 1/2[/math];

[math]p_0 / 2 + (p_0 - 1)\varepsilon \gt 0[/math];

[math]\varepsilon \lt \frac{p_0}{2 (1 - p_0)}[/math].

Достаточно взять [math]\varepsilon \le p_0 / 2[/math]. Из сделанного выше замечания следует, что работу функции infair_coin() можно смоделировать с помощью не более чем [math]s(n) + 1[/math] вызовов random(). Таким образом, мы построили программу [math]q[/math], удовлетворяющую ограничениям класса [math]\mathrm{PP}[/math].

3. [math]\mathrm{PP} \subset \mathrm{PS}[/math]. Пусть [math]p[/math] — программа для языка [math]L \in \mathrm{PP}[/math]. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для [math]\mathrm{PS}[/math] будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них [math]p[/math]. Ответом будет [math]0[/math] или [math]1[/math] в зависимости от того, каких ответов [math]p[/math] оказалось больше.
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]p[/math] — программа для [math]L \in \mathrm{RP}[/math]. Программу [math]q[/math] для [math]\mathrm{BPP}[/math] определим следующим образом: 

 q(x)
   u <- p(x)
   v <- p(x)
   return u or v

Пусть [math]x \in L[/math]. В этом случае вероятность ошибки равна [math]\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4[/math].

Пусть [math]x \notin L[/math]. Тогда с вероятностью [math]1[/math] будет верно [math]u = 0, v = 0[/math] и [math]q[/math] вернет правильный ответ.

Аналогично доказывается, что [math]\mathrm{coRP} \subset \mathrm{BPP}[/math].
[math]\triangleleft[/math]

См. также

Литература

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Вероятностные_вычисления._Вероятностная_машина_Тьюринга&oldid=23430»