Изменения

{{В разработке}}[[Категория: Теория сложности]]Здесь будет введение'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.

'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов. Распределение битов на ленте , распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</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> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что утверждениялюбой предикат от ВМТ является событием.{{Теорема|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> измеримо.|proof=<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> следует, являются событиямичто они дизъюнктны.+ матожидание будем считать по пространству лент

<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{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:1) <tex>\operatorname{P}(p(x) \ne [x R \in L]) = 0</tex>;<br>2) <tex>\operatorname{E}(\operatorname{T}(p(x))) = poly(|x|)</tex>.<br>}} {{Определение|definition =<tex>\mathrm{RP}</tex> (от ''randomized polynomial'') — множество языков <tex>LSigma</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{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(xR) = [x \in L]) sum\ge 2/3</tex>;<br>2) <tex>\operatornamelimits_{T}(p(x)) \le poly(|x|)</tex>.}i = 0}Аналогично сделанному выше замечанию, константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>. Замена константы на <tex>1/2</tex> сделало бы данный класс равным <tex>\Sigma^*</tex>. {{Определение|definition =<tex>\mathrm{PPinfty}</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|R_i)</tex>.

== Соотношение вероятностных классов См. также ==* [[Классы RP и coRP]]* [[Класс ZPP]]* [[Класс BPP]]