Изменения
Новая страница: «===Определения=== Классом <tex>ZPP</tex> называется множество языков, для которых существует [[Вер…»
===Определения===
Классом <tex>ZPP</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] такая, что математическое ожидание времени ее работы на входе длинны <tex>n</tex> равно <tex>O(poly(n))</tex>.
<tex>ZPP = \{ L | \exists m : L(m)=L, E(T(m(x))) = O(poly(|x|)) \}</tex>
===Альтернативное определения===
Классом <tex>ZPP^{'}</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m</tex> такая, что временя ее работы на входе длинны <tex>n</tex> не превосходит <tex>poly(n)</tex>. У <tex>m</tex> есть три конечных состояния: 'да', 'нет', 'не знаю' и <tex>p(m(x) = </tex>'не знаю'<tex>) \le \frac{1}{2}</tex>
<tex>ZPP^{'} = \{ L | \exists m : L(m)=L, T(m(x)) \le poly(|x|) p(m(x) = ?) \le \frac{1}{2} \}</tex>.
Классом <tex>ZPP</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] такая, что математическое ожидание времени ее работы на входе длинны <tex>n</tex> равно <tex>O(poly(n))</tex>.
<tex>ZPP = \{ L | \exists m : L(m)=L, E(T(m(x))) = O(poly(|x|)) \}</tex>
===Альтернативное определения===
Классом <tex>ZPP^{'}</tex> называется множество языков, для которых существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m</tex> такая, что временя ее работы на входе длинны <tex>n</tex> не превосходит <tex>poly(n)</tex>. У <tex>m</tex> есть три конечных состояния: 'да', 'нет', 'не знаю' и <tex>p(m(x) = </tex>'не знаю'<tex>) \le \frac{1}{2}</tex>
<tex>ZPP^{'} = \{ L | \exists m : L(m)=L, T(m(x)) \le poly(|x|) p(m(x) = ?) \le \frac{1}{2} \}</tex>.
