Изменения

<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:

1) <tex>\operatorname{P}(p(x) = [x \in L]) \ge 2/3</tex>;<br>

}}

Аналогично сделанному выше замечанию, константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>. Замена константы на <tex>1/2</tex> сделало бы данный класс равным <tex>\Sigma^*</tex>.

<tex>\mathrm{PP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:

1) <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;<br>

}}