Здесь {{Определение|definition =<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:# <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br># <tex>\operatorname{E}[\operatorname{T}(p, x)] = poly(|x|)</tex>.<br>}}<tex>\mathrm{ZPP}</tex> — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае. Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу <tex>x</tex>. {{Теорема|statement = <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.|proof =Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, удовлетворяющие ограничениям <tex>\mathrm{P}</tex>, также удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>. Покажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.Для этого определим вспомогательный класс <tex>\mathrm{ZPP}_1</tex>.{{Определение|definition =<tex>\mathrm{ZPP}_1</tex> — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:# <tex>p(x) \in \{0, 1, ?\}</tex>;# <tex>p(x) \ne \enskip? \Rightarrow p(x) = [x \in L]</tex>;# <tex>\operatorname{P}(p(x) = \enskip?) \le 1/2</tex>;# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|).</tex>}}1. Сначала докажем, что <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex>. 1) <tex>\mathrm{ZPP} \subset \mathrm{ZPP}_1</tex>. Пусть <tex>X</tex> — случайная величина, равная времени работы программы <tex>p</tex> для <tex>\mathrm{ZPP}</tex>, <tex>X > 0</tex>. Запишем [http://ru.wikipedia.org/wiki/Неравенство_Маркова неравенство Маркова]: <tex>\operatorname{P}(X > k \operatorname{E}[X]) \le 1/k</tex>. Подставим <tex>k = 2</tex>. Тогда, если запустить программу <tex>p</tex> для <tex>\mathrm{ZPP}</tex> с ограничением по времени <tex>2E[X]</tex>, она не успеет завершиться с вероятностью, не превышающей <tex>1/2</tex>. Опишем программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>. Она будет статьявозвращать <tex>?</tex>, если <tex>p</tex> не успеет завершиться, а иначе — результат работы программы <tex>p</tex>. Заметим, что <tex>q</tex> работает полиномиальное время, так как <tex>E[X]</tex> ограничено некоторым полиномом по определению класса <tex>\mathrm{ZPP}</tex>. 2) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>.Будем запускать программу <tex>p</tex> для <tex>\mathrm{ZPP_1}</tex>, пока не получим ответ, отличный от <tex>?</tex>. Математическое ожидание количества запусков <tex>p</tex> не превышает <tex>\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2</tex>. Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса <tex>\mathrm{ZPP}</tex>. 2. Теперь покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>. 1) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>0</tex>. 2) <tex>\mathrm{ZPP}_1 \subset\mathrm{coRP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>1</tex>. 3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>: <tex>q</tex>(x) '''if''' <tex>p_2</tex>(x) = 0 '''return''' 0 '''if''' <tex>p_1</tex>(x) = 1 '''return''' 1 '''return''' ? Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2</tex>.}} == Литература ==* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak.Computational Complexity: A Modern Approach]
