Изменения

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

Навигация