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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 +
{{В разработке}}
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
+
Здесь будет введение.
  
 +
== Основные определения ==
 
{{Определение
 
{{Определение
 
|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> — вероятностная лента.
 +
 
 +
Здесь будет теорема о том, что утверждения, связанные с ВМТ, являются событиями.
 +
+ матожидание будем считать по пространству лент
 +
 
 +
== Вероятностные сложностные классы ==
 +
 
 +
Теперь введем некоторые сложностные классы.
  
Введем [http://ru.wikipedia.org/wiki/Вероятностное_пространство вероятностное пространство] <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Будем считать, что <tex>\Sigma</tex> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.
+
{{Определение
{{Теорема
+
|definition =
|statement= Пусть <tex>m</tex> — ВМТ. Тогда для любых <tex>x</tex> и <tex>A</tex> — предиката от <tex>m</tex> выполняется <tex>R = \{r \bigm| A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.
+
<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
|proof=
+
1) <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>
<tex>R = \bigcup\limits_{i = 0}^\infty R_i</tex>, где <tex>R_i = \{r \bigm| A(m(x, r)), m</tex> прочитала ровно <tex>i</tex> первых символов с <tex>r\}</tex>. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения <tex>R_i</tex> следует, что они дизъюнктны.
+
2) <tex>\operatorname{E}(\operatorname{T}(p(x))) = poly(|x|)</tex>.<br>
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
<tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
 +
1) <tex>x \notin L \Rightarrow p(x) = 0</tex>;<br>
 +
2) <tex>x \in L \Rightarrow \operatorname{P}(p(x) = 1) \ge 1/2</tex>;<br>
 +
3) <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>
 +
}}
 +
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
 +
Определим также <tex>\mathrm{coRP}</tex> как дополнение к <tex>\mathrm{RP}</tex>.
 +
 
 +
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
 +
 
 +
{{Определение
 +
|definition =
 +
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
 +
1) <tex>\operatorname{P}(p(x) = [x \in L]) \ge 2/3</tex>;<br>
 +
2) <tex>\operatorname{T}(p(x)) \le poly(|x|)</tex>.
 +
}}
 +
Аналогично сделанному выше замечанию, константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>. Замена константы на <tex>1/2</tex> сделало бы данный класс равным <tex>\Sigma^*</tex>.
  
<tex>R_i \in \Sigma</tex> как зависящие от <tex>i</tex> первых битов вероятностной ленты, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s \bigm| |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>.
+
{{Определение
 +
|definition =
 +
<tex>\mathrm{PP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
 +
1) <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;<br>
 +
2) <tex>\operatorname{T}(p(x)) \le poly(|x|)</tex>.
 +
}}
  
<tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.
+
== Соотношение вероятностных классов ==
 +
{{Теорема
 +
|statement =
 +
1. <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>
 +
2. <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>
 +
3. <tex>\mathrm{RP} \subset \mathrm{BPP}</tex>
 +
|proof =
 +
1. Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, разрешающие <tex>\mathrm{P}</tex>, удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.
 +
<br>
 +
Покажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
 +
...
 +
<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> оказалось больше.
 +
3. ...
 
}}
 
}}
  
== См. также ==
 
* [[Классы RP и coRP]]
 
* [[Класс ZPP]]
 
* [[Класс BPP]]
 
  
 
== Литература ==
 
== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: