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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 70: Строка 70:
 
<br>
 
<br>
 
2. Покажем, что <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> оказалось больше.
 
2. Покажем, что <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> оказалось больше.
 +
<br>
 +
Теперь докажем, что <tex>\mathrm{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>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(c) ? 1 : infair_coin()
 +
...
 +
 
3. ...
 
3. ...
 
}}
 
}}
  
 +
== См. также ==
 +
* [[Теоремы о BPP, BPPweak и BPPstrong]]
 +
* [[Теорема Лаутемана]]
  
 
== Литература ==
 
== Литература ==
 +
* [http://www.cs.princeton.edu/theory/complexity/book.pdf Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

Версия 03:27, 30 мая 2012

Эта статья находится в разработке!

Здесь будет введение.

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

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


Определение:
Вероятностной машиной Тьюринга будем называть машину Тьюринга, имеющее доступ к вероятностной ленте.


При интерпретации вероятностной машины Тьюринга как программы, обращение к очередному биту можно трактовать как вызов специальной функции random(). При этом также будем предполагать, что вероятностная лента является неявным аргументом для программы, т.е. [math]p(x) = p(x, r)[/math], где [math]r[/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{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]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(c) ? 1 : infair_coin()

...

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

См. также

Литература