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

Определения

Классом [math]ZPP[/math] называется множество языков, для которых существует вероятностная машина Тьюринга такая, что математическое ожидание времени ее работы на входе длинны [math]n[/math] равно [math]O(poly(n))[/math].

[math]ZPP = \{ L | \exists m : L(m)=L, E(T(m(x))) = O(poly(|x|)) \}[/math]

Альтернативное определения

Классом [math]ZPP^{'}[/math] называется множество языков, для которых существует вероятностная машина Тьюринга [math]m[/math] такая, что временя ее работы на входе длинны [math]n[/math] не превосходит [math]poly(n)[/math]. У [math]m[/math] есть три конечных состояния: 'да', 'нет', 'не знаю' и [math]p(m(x) = [/math]'не знаю'[math]) \le \frac{1}{2}[/math]

[math]ZPP^{'} = \{ L | \exists m : L(m)=L, T(m(x)) \le poly(|x|) p(m(x) = ?) \le \frac{1}{2} \}[/math].