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