322
правки
Изменения
→См. также
[[Категория: Теория сложности]]
'''Вероятностные вычисления ''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ , говоря неформально, к случайным битамгенератору случайных чисел. Мы рассмотрим классы сложности, для которых разрешающие программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
{{Определение
|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.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>\forall A</tex> — предикат предиката от ВМТ: <tex>m</tex> выполняется <tex>R = \{r \bigm| A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.
|proof=
<tex>R = R_i \bigcupin \limits_{Sigma</tex> как зависящие от <tex>i = 0}^\infty R_i</tex>первых битов вероятностной ленты, <tex>\operatorname{P}(R_i ) = \frac{r 1}{2^i} \cdot |\{s \bigm| |s| A(m(x= i, r)), ms</tex> прочитала ровно <tex>i</tex> первых символов с вероятностной ленты— префикс <tex>r \in R_i\}|</tex>.
}}
== См. также ==
* [[Теоремы о BPP, BPPweak Классы RP и BPPstrongcoRP]]* [[Уменьшение ошибки в классе RPКласс ZPP]]* [[Теорема ЛаутеманаКласс BPP]]
== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]