205
правок
Изменения
м
== Вероятностные классы сложности ==
{{Определение
|definition =
<tex>\mathrm{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|)</tex>.
}}
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.
→Вероятностные классы сложности
<tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.
}}
== Соотношение вероятностных классов ==
