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. Для алгоритма из co-RP рассуждение проводится аналогично.



Wikimedia Foundation. 2010.

Поможем студентам написать доклад

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

  • ZPP — steht als Abkürzung für: ZPP (Komplexitätsklasse), Komplexitätsklasse ein Gemisch für Feststoffraketen, siehe Anfeuerungssatz Związek Patriotów Polskich (Bund polnischer Patrioten), eine moskautreue polnische Exilantenorganisation in der UdSSR …   Deutsch Wikipedia

  • ZPP — This is an article about a computational complexity class. For Polish communist political organisation, see Związek Patriotów Polskich . For the pyrotechnic composition, see zirconium potassium perchlorate.In complexity theory, ZPP (Zero error… …   Wikipedia

  • ZPP — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

  • ZPP — Zero error Probabilistic Polynomial (Academic & Science » Mathematics) * Zoo Pilot Publishing (Business » Firms) * Zoo Pilot Publishing (Community » Media) …   Abbreviations dictionary

  • ZPP — zinc protoporphyrin …   Medical dictionary

  • zpp — ISO 639 3 Code of Language ISO 639 2/B Code : ISO 639 2/T Code : ISO 639 1 Code : Scope : Individual Language Type : Living Language Name : El Alto Zapotec Macrolanguages : Identifier : (ISO 639 3) : zap Macrolanguages : Name : Zapotec Individual …   Names of Languages ISO 639-3

  • ZPP — abbr. Zinc Proto Porphyrin …   Dictionary of abbreviations

  • ZPP — • zinc protoporphyrin …   Dictionary of medical acronyms & abbreviations

  • ZPP (Komplexitätsklasse) — Die Komplexitätsklasse ZPP oder ZPP( ) (Zero error Probabilistic Polynomial Time) beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen …   Deutsch Wikipedia

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


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

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