WikiSort.ru - Не сортированное

В теории вычислительной сложности, 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. Для доказательства включения ZPP в co-RP можно либо воспользоваться тем же рассуждением, либо заметить, что ZPP замкнут относительно взятия дополнения.

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 13 мая 2011 года.