Сложностный класс BPP

Определение класса PP

Классом [math]\mbox{PP}[/math] называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа. [math]ZPP^{'} = \{ L | \exists m : L(m)=L, T(m(x)) \le poly(|x|) p(m(x) = ?) \le \frac{1}{2} \}[/math]. [math]PP = \{L | \exists m : P(m(x) = [x \in L]) \g \frac{1}{2} \}[/math] В этом определениях [math]m[/math] - это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входа.

Определение класса BPP

[math]BPP = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) \gt 2/3 \}[/math]
где [math]m[/math] -- вероятностная машина Тьюринга.