322
правки
Изменения
→Вероятностные сложностные классы
# <tex>\operatorname{E}[\operatorname{T}(p(x))] = poly(|x|)</tex>.<br>
}}
<tex>\mathrm{ZPP}</tex> — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.
Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу <tex>x</tex>.
{{Определение
# <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|).</tex>
}}
<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
<tex>\mathrm{coRP} = \{L | \overline L \in \mathrm{RP}\}</tex>.
}}
Класс <tex>\mathrm{coRP}</tex> допускает ошибки программ на словах, не принадлежащих <tex>L</tex>.
{{Определение
|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>;<br>
# <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 =
<tex>\mathrm{PP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;<br>
# <tex>\forall r \operatorname{T}(p(x)) \le poly(|x|)</tex>.
}}
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.
== Соотношение вероятностных классов ==
