Класс ZPP

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

Классы сложности алгоритмов
 
Cчитаются лёгкими P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов


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

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Класс ZPP" в других словарях:

  • ZPP — В теории вычислительной сложности, ZPP (zero error probabilistic polynomial time безошибочный вероятностный полиномиальный) это такой класс задач, для которых существует вероятностная машина Тьюринга, удовлетворяющая нескольким свойствам: Она… …   Википедия

  • Класс RP — Будем считать, что язык L принадлежит классу RP («randomized polynomial class»  случайный полиномиальный), если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия: Если w не принадлежит L, то вероятность …   Википедия

  • Класс сложности — В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0… …   Википедия

  • Класс NP — В теории алгоритмов классом NP (от англ. non deterministic polynomial) называют множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за… …   Википедия

  • Класс PH — В теории алгоритмов классом сложности PH (от англ. polynomial hierarchy) называется объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит… …   Википедия

  • Класс BPP — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Класс ВPP — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Класс P — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отр …   Википедия

  • Класс co-NP — В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP,  класс дополнений языков из NP, называемый co NP. Формальное определение Класс сложности co NP определяется для множества языков, то есть множеств слов над конечным… …   Википедия

  • Класс сo-NP — В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP, класс дополнений языков из NP, называемый co NP. Формальное определение Класс сложности co NP определяется для множества языков, т.е. множеств слов над конечным алфавитом… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»