Машина Тьюринга всегда работает за полиномиальное время.
Она отвечает «Да», «Нет» или «Не знаю».
Ответ может быть либо правильным, либо «Не знаю».
Машина Тьюринга отвечает «Не знаю» с вероятностью не больше ½.
Выбор одного из двух наборов свойств приводит к эквивалентным определениям класса ZPP. Машину Тьюринга, удовлетворяющую этим свойствам, иногда называют машиной Тьюринга типа Лас-Вегас.
Эквивалентное определение через пересечение
Класс ZPP равен пересечению классов RP и Co-RP. Часто именно это принимается за определение ZPP. Чтобы продемонстрировать это, заметим, что любая задача принадлежащая одновременноRP и co-RP имеет алгоритм типа Лас-Вегас:
Допустим, существует язык L, распознаваемый RP-алгоритмом A и (возможно отличным от A) co-RP-алгоритмом B.
Выполним один шаг алгоритма A на входной последовательности. Если будет возвращен ответ «Да», то окончательный ответ должен быть «Да». В противном случае запустим один шаг алгоритма B с тем же входом. Если он ответит «Нет», то окончательный ответ должен быть «Нет». Если не выполнено ни одно из предыдущих условий, повторим данный шаг.
Заметим, что лишь один из алгоритмов A или B может дать неправильный ответ, и вероятность этого события равняется на каждом шаге 50 %. Таким образом, вероятность достигнуть k-го шага уменьшается экспоненциально относительно k. Это показывает, что математическое ожидание времени работы полиномиально. Из сказанного следует, что пересечение классов RP и co-RP содержится в ZPP.
Покажем, что ZPP содержится в пересечении RP и co-RP. Пусть имеется машина Тьюринга типа Лас-Вегас C, которая решает задачу. Обозначим математическое ожидание времени её работы за M (по условию, оно конечно). Тогда можно построить следующий RP алгоритм:
Запустим C на время, не меньшее 2M. Если за это время C получила ответ — возвращаем его. Если до момента останова никакого ответа не получено, говорим «Нет».
Вероятность того, что ответ будет получен до момента останова, равняется ½ (из неравенства Маркова). Это в свою очередь означает, что вероятность ответа «Нет» при правильном ответе «Да» (такое могло случиться из-за преждевременной остановки C), равна ½, что удовлетворяет определению RP. Для доказательства включения ZPP в co-RP можно либо воспользоваться тем же рассуждением, либо заметить, что ZPPзамкнут относительно взятия дополнения.
