205
правок
Изменения
м
→Определения
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}
{{Определение
|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>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
