editor
143
правки
Изменения
Нет описания правки
==Определения==
{{Определение
|definition =
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall 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> — сложностный класс, допускающий двусторонние ошибки.
Аналогично сделанному выше замечанию, константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>. Замена константы на <tex>1/2</tex> сделало бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).
{{Определение
|definition=
