322
правки
Изменения
Нет описания правки
{{Определение
|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 \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>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{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>.
{{Определение
|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>.
}}
== Соотношение вероятностных классов ==
== Литература ==
