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