31
правка
Изменения
→Определения
{{Определение
|definition =
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>\exists p \forall </tex>, что для любого <tex>x</tex>:# <tex>\operatorname{P}(p(x) = [x \in L]) \ge 2/3</tex>;# <tex>\forall r \operatorname{T}(p, (x)) \le poly(|x|)</tex>для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}
<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
{{Определение
|definition=
<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p(x)) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}
