Изменения
→Доказательство
==Доказательство==
*<tex>1)ZPP \supset ZPP^{'}</tex>
Пусть язык <tex>L \in ZPP^{'}</tex>, тогда для него существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m_1</tex>. Построим [[Вероятностная машина Тьюринга|вероятностную машину Тьюринга]] <tex>m_2</tex>, которая на входе <tex>x</tex> работает следущим образом:
<tex>E(T(m_2(x)))= \sum_{i}^{ \infty } poly(x)*\cdot p^i*\cdot i = poly(x) * \cdot \sum_{i}^{ \infty } \frac{i}{2^i}</tex>
<tex>\sum_{i}^{ \infty } \frac{i}{2^i}</tex> сходится.
Таким образом <tex>E(T(m_2(x)))=O(plolypoly(|x|))</tex>, значит <tex>ZPP \supset ZPP^{'}</tex>.
*<tex>2)ZPP \subset ZPP^{'}</tex>
Пусть язык <tex>L \in ZPP</tex>, тогда для него существует [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]] <tex>m_1</tex> такая, что <tex>E(T(m_1(x))) \le p(|x|)</tex>, где <tex>p \in poly</tex>.
Сделаем машину <tex>m_2</tex>, которая будет запускать <tex>m_1</tex> на <tex>2*\cdot p(|x|)</tex> шагов, если <tex>m_1</tex> не завершила свою работу, то <tex>m_2</tex> выдаст 'не знаю', в противном случаи вернет результат работы <tex>m_1</tex>.
Пусть <tex>p(m_1(x) = ?) > \frac{1}{2}</tex>, тогда <tex>E(T(m_1(x))) > p(|x|)</tex> — противоречие.
