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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Соотношение вероятностных классов)
(Основные определения)
Строка 6: Строка 6:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Вероятностная лента''' — бесконечная последовательность битов. Распределение битов на ленте подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
+
'''Вероятностная лента''' — бесконечная последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Вероятностной машиной Тьюринга''' будем называть машину Тьюринга, имеющее доступ к вероятностной ленте.
+
'''Вероятностная машина Тьюринга''' (ВМТ) — обобщение детерминированной машины Тьюринга. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.
 
}}
 
}}
  
При интерпретации вероятностной машины Тьюринга как программы, обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом для программы, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
+
Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
<br>
 
В дальнейшем все вероятностные соображения будут относиться к пространству вероятностных лент <tex>r</tex>, вход же программы <tex>x</tex> будем считать фиксированным.
 
  
Здесь будет теорема о том, что утверждения, связанные с ВМТ, являются событиями.
+
Введем вероятностное пространство <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Покажем, что любой предикат от ВМТ является событием.
 +
{{Теорема
 +
|statement= <tex>\forall A</tex> — предикат от ВМТ: <tex>R = \{r | A(m(x, r))\} \in \Sigma</tex>.
 +
|proof=
 +
Считаем, что <tex>x</tex> фиксирован.
  
 +
<tex>R = \bigcup\limits_{i = 0}^\infty R_i</tex>, <tex>R_i = \{r | A(m(x, r)), m</tex> прочитала ровно <tex>i</tex> первых символов с вероятностной ленты<tex>\}</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>.
 +
}}
  
 
== Вероятностные сложностные классы ==
 
== Вероятностные сложностные классы ==

Версия 21:11, 30 мая 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]\forall A[/math] — предикат от ВМТ: [math]R = \{r | A(m(x, r))\} \in \Sigma[/math].
Доказательство:
[math]\triangleright[/math]

Считаем, что [math]x[/math] фиксирован.

[math]R = \bigcup\limits_{i = 0}^\infty R_i[/math], [math]R_i = \{r | A(m(x, r)), m[/math] прочитала ровно [math]i[/math] первых символов с вероятностной ленты[math]\}[/math].

[math]R_i \in \Sigma[/math], [math]\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s : |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{RP}[/math] (от randomized polynomial) — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:

1) [math]x \notin L \Rightarrow p(x) = 0[/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]1/2[/math] в пункте 2 определения [math]\mathrm{RP}[/math] может быть заменена на любую другую из промежутка [math](0, 1)[/math], поскольку требуемой вероятности можно добиться множественным запуском программы. Определим также [math]\mathrm{coRP}[/math] как дополнение к [math]\mathrm{RP}[/math].

[math]\mathrm{RP}[/math] можно рассматривать как вероятностный аналог класса [math]\mathrm{NP}[/math], предполагая, что вероятность угадать сертификат в случае его существования не менее [math]1/2[/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]\operatorname{T}(p(x)) \le poly(|x|)[/math].

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


Определение:
[math]\mathrm{PP}[/math] (от bounded 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]\operatorname{T}(p(x)) \le poly(|x|)[/math].


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

Теорема:
1. [math]\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math]

2. [math]\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}[/math]

3. [math]\mathrm{RP} \subset \mathrm{BPP}[/math]
Доказательство:
[math]\triangleright[/math]

1. Утверждение [math]\mathrm{P} \subset \mathrm{ZPP}[/math] является очевидным, так как программы, разрешающие [math]\mathrm{P}[/math], удовлетворяют ограничениям класса [math]\mathrm{ZPP}[/math].
Покажем, что [math]\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math]. ...
2. Покажем, что [math]\mathrm{RP} \subset \mathrm{NP}[/math]. Если в разрешающей программе для [math]L \in \mathrm{RP}[/math] заменить все вызовы random() на недетерминированный выбор, то получим программу с ограничениями [math]\mathrm{NP}[/math], разрешающую [math]L[/math].
Покажем, что [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]\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 <- случайный сертификат (полиномиальной длины)
   return V(x, c) ? 1 : infair_coin()

Необходимо удовлетворить условию [math]\operatorname{P}(p(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}(p(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)[/math], где [math]p_0[/math] — вероятность угадать правильный сертификат. Заметим, что поскольку все сертификаты имеют полиномиальную длину и существует хотя бы один правильный сертификат, [math]p_0[/math] не более чем экспоненциально мала. Найдем [math]\varepsilon[/math] из неравенства [math]\operatorname{P}(p(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 p_0 (1 - p_0) / 2[/math].

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


3. ...
[math]\triangleleft[/math]

См. также

Литература