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

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

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