202
правки
Изменения
кат
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}
<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).
{{Определение
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.
{{Определение
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>
* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]
* [http://en.wikipedia.org/wiki/PP_(complexity) Wikipedia — PP compexity class]
* [http://en.wikipedia.org/wiki/Bounded-error_probabilistic_polynomial Wikipedia — BPP complexity class]
[[Категория:Классы сложности]][[Категория: Теория сложностиформальных языков]]
