Изменения
→Определения
{{Определение
|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> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
{{Определение
|definition=
<tex>\mathrm{BPP_{strong}}</tex> — множество класс языков <tex>L</tex>, для которых существует <tex>p</tex>, такая, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - 1 / {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p(x)) \le poly(|x|)</tex> для любой вероятностной ленты.
