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

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

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

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

Классом [math]\mbox{BPP}[/math] (от англ. bounded-error, probabilistic, polynomial) называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше [math]\frac{2}{3}[/math] и время ее работы ограничено полиномом от длины входа. [math]\mbox{BPP} = \{L | \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) \gt \frac{2}{3} \}[/math] , где [math]m[/math] -- вероятностная машина Тьюринга.