Изменения

<tex>\mathrm{ZPP}_1</tex> — множество языков <tex>L</tex>, для которых <tex>\exists p, p(x) \in \{0, 1, ?\}, \forall x</tex>:1) <tex>p(x) \ne in \{0, 1, ? \Rightarrow p(x) = [x \in L]}</tex>;

2) <tex>p(x) \ne ? \operatorname{P}(Rightarrow p(x) = ?) [x \le 1/2in L]</tex>;

3) <tex>\operatorname{P}(p(x) = ?) \le 1/2</tex>; 4) <tex>\operatorname{T}(p(x)) \le poly(|x|).</tex>

1) <tex>\mathrm{ZPP} \subset \mathrm{ZPP}_1</tex>.  Пусть <tex>X</tex> — случайная величина, равная времени работы программы <tex>p</tex> для <tex>\mathrm{ZPP}</tex>. Запишем частный случай [http://ru.wikipedia.org/wiki/Неравенство_Маркова неравенства Маркова]: <tex>\operatorname{P}(X > k \operatorname{E}[X]) \le 1/k</tex>...

2) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>. Будем запускать программу p для <tex>\mathrm{ZPP_1}</tex>, пока не получим ответ, отличный от ?.Математическое ожидание количества запусков <tex>p</tex> не превышает <tex>\sum\limits_{k = 0}^\infty \frac{k}{2^k} = 2</tex>.Значит, новая программа будет в среднем работать за полиномиальное время, что и требуется для класса <tex>\mathrm{ZPP}</tex>.