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

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

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

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

Определение:

Вероятностная лента — бесконечная последовательность битов. Распределение битов на ленте подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения [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{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].