322
правки
Изменения
→Соотношение вероятностных классов
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>ZPP</tex> с ограничением по времени <tex>2E[X]</tex>, она не успеет завершиться с вероятностью, не превышающей <tex>1/2</tex>.В этом случае программа <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex> вернет <tex>?</tex>, а иначе — результат программы <tex>p</tex>.Заметим, что <tex>q</tex> работает полиномиальное время, так как <tex>E[X]</tex> ограничено некоторым полиномом по определению класса <tex>\mathrm{ZPP}</tex>.
2) <tex>\mathrm{ZPP_1} \subset \mathrm{ZPP}</tex>. Будем запускать программу p для <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>.
