1632
правки
Изменения
м
rollbackEdits.php mass rollback
===Определения===
Классом <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>, которое более удобно.
