WikiDer > ЗПП (сложность)

ZPP (complexity)
Схема рандомизированных классов сложности
ЗПП по отношению к другим классам вероятностной сложности (RP, co-RP, BPP, BQP, PP), которые обобщают п в PSPACE. Неизвестно, являются ли какие-либо из этих условий строгими.

В теория сложности, ЗПП (вероятностный полиномиальное время) это класс сложности проблем, для которых вероятностная машина Тьюринга существует с этими свойствами:

  • Он всегда возвращает правильный ответ ДА ​​или НЕТ.
  • Время работы полиномиально от ожидания для каждого ввода.

Другими словами, если алгоритму разрешено подбрасывать действительно случайную монету во время его работы, он всегда будет возвращать правильный ответ, а в случае проблемы с размером п, есть полином п(п) так, что среднее время работы будет меньше п(п), хотя иногда может быть намного дольше. Такой алгоритм называется Алгоритм Лас-Вегаса.

В качестве альтернативы, ЗПП можно определить как класс задач, для которых вероятностная машина Тьюринга существует с этими свойствами:

  • Он всегда выполняется за полиномиальное время.
  • Он возвращает ответ ДА, НЕТ или НЕ ЗНАЮ.
  • Ответ всегда либо НЕ ЗНАЮ, либо правильный ответ.
  • Он возвращает НЕ ЗНАЮ с вероятностью не более 1/2 (в противном случае - правильный ответ).

Эти два определения эквивалентны.

Определение ЗПП основан на вероятностных машинах Тьюринга, но для ясности отметим, что другие классы сложности, основанные на них, включают BPP и RP. Класс BQP основан на другой машине со случайностью: квантовый компьютер.

Определение пересечения

Класс ЗПП в точности равно пересечению классов RP и co-RP. Это часто принимают за определение ЗПП. Чтобы показать это, сначала обратите внимание, что каждая проблема, которая находится в обе RP и co-RP имеет Алгоритм Лас-Вегаса следующее:

  • Предположим, у нас есть язык L, распознаваемый как RP алгоритм A и (возможно, совершенно разные) co-RP алгоритм Б.
  • Учитывая ввод, запустите A на входе для одного шага. Если он возвращает ДА, ответ должен быть ДА. В противном случае запустите B на входе для одного шага. Если он возвращает НЕТ, ответ должен быть НЕТ. Если ничего не происходит, повторите этот шаг.

Обратите внимание, что только одна машина может дать неправильный ответ, и вероятность того, что эта машина даст неправильный ответ во время каждого повторения, составляет не более 50%. Это означает, что шанс достижения k-й раунд экспоненциально сжимается в k, показывая, что ожидал время работы полиномиальное. Это показывает, что RP пересекаться co-RP содержится в ЗПП.

Чтобы показать это ЗПП содержится в RP пересекаться co-RP, предположим, у нас есть алгоритм C Лас-Вегаса для решения проблемы. Затем мы можем построить следующие RP алгоритм:

  • Запустите C хотя бы двойной ожидаемое время работы. Если он дает ответ, дайте этот ответ. Если он не дает ответа до того, как мы его остановим, дайте НЕТ.

К Неравенство Маркова, вероятность того, что он даст ответ до того, как мы остановимся, составляет не менее 1/2. Это означает, что вероятность того, что мы дадим неправильный ответ в случае ДА, остановившись и получив НЕТ, составляет не более 1/2, что соответствует определению RP алгоритм. В co-RP алгоритм идентичен, за исключением того, что он дает ДА, если C "истекает".

Свидетели и доказательства

Классы НП, RP и ЗПП можно рассматривать как доказательство принадлежности к набору.

Определение: А верификатор V для множества X - это машина Тьюринга, такая что:

  • если Икс в Икс тогда существует строка ш такой, что V(Икс,ш) принимает;
  • если Икс не в Икс, то для всех строк ш, V(Икс,ш) отклоняет.

Струна ш можно рассматривать как доказательство членства. В случае коротких доказательств (длина которых ограничена полиномом от размера входных данных), которые можно эффективно проверить (V является детерминированной машиной Тьюринга с полиномиальным временем), строка ш называется свидетель.

Примечания:

  • Определение очень асимметричное. Доказательство того, что x находится в X, - это одна строка. Доказательство того, что x не принадлежит X, - это набор всех строк, ни одна из которых не является доказательством принадлежности.
  • Доступность свидетеля одинакова. Для всех x в X должен быть свидетель. Это не тот случай, когда некоторые x в X слишком сложно проверить, в то время как большинство - нет.
  • Свидетель не обязательно должен быть традиционным доказательством. Если V - вероятностная машина Тьюринга, которая, возможно, могла бы принять x, если x находится в X, то доказательством является цепочка подбрасываний монеты, которая приводит машину, благодаря удаче, интуиции или гению, к принятию Икс.
  • Совместная концепция является доказательством непринадлежности или принадлежности к набору дополнений.

Классы НП, RP и ЗПП - это наборы, у которых есть свидетели членства. Класс НП требуется только наличие свидетелей. Они могут быть очень редкими. Из 2ж(|Икс|) возможные строки, с ж многочлен, только одно нужно заставить верификатор принять (если x находится в X. Если x не находится в X, никакая строка не заставит верификатор принять).

Для классов RP и ЗПП любая строка, выбранная наугад, скорее всего, будет свидетелем.

Соответствующие классы имеют свидетельство о неприсоединении. Особенно, co-RP - это класс множеств, для которых, если x не входит в X, любая случайно выбранная строка, вероятно, будет свидетельством отсутствия членства. ЗПП - это класс наборов, для которых любая случайная строка может быть свидетелем x в X или x не в X, в любом случае.

Связывая это определение с другими определениями RP, co-RP и ЗПП это просто. Вероятностная машина Тьюринга с полиномиальным временем V *ш(Икс) соответствует детерминированной машине Тьюринга с полиномиальным временем V(Икс, ш) путем замены случайной ленты V * со второй входной лентой для V, на которой написана последовательность подбрасываний монеты. Выбирая свидетеля в качестве случайной строки, верификатор становится вероятностной машиной Тьюринга с полиномиальным временем, вероятность принятия x, когда x находится в Икс большой (скажем, больше 1/2), но ноль, если ИксИкс (за RP); отклонения x, когда x не в X, велико, но равно нулю, если ИксИкс (за co-RP); и правильно принять или отклонить Икс как член Икс велико, но ноль неверного принятия или отклонения x (для ЗПП).

Путем повторного случайного выбора возможного свидетеля большая вероятность того, что случайная строка является свидетелем, дает ожидаемый полиномиальный алгоритм времени для принятия или отклонения ввода. И наоборот, если ожидается, что машина Тьюринга будет работать за полиномиальное время (для любого заданного x), тогда значительная часть прогонов должна быть ограничена полиномиальным временем, и последовательность монет, используемая в таком прогоне, будет свидетелем.

ЗПП следует противопоставить BPP. Класс BPP не требует свидетелей, хотя свидетелей достаточно (следовательно, BPP содержит RP, co-RP и ЗПП). А BPP в языке V (x, w) принимает (явное) большинство строк w, если x находится в X, и, наоборот, отклоняет (явное) большинство строк w, если x не находится в Икс. Никакая отдельная строка w не должна быть окончательной, и поэтому они, как правило, не могут считаться доказательствами или свидетелями.

Теоретико-сложные свойства

Известно, что ZPP замкнута относительно дополнения; то есть ZPP = co-ZPP.

ЗПП - это низкий для самого себя, что означает, что машина ZPP, способная мгновенно решать проблемы ZPP (машина-оракул ZPP), не более мощная, чем машина без этой дополнительной мощности. В символах ЗППЗПП = ЗПП.

ЗППНПBPP = ЗППНП.

НПBPP содержится в ЗППНП.

Подключение к другим классам

С ЗПП = RPcoRP, ЗПП очевидно содержится в обоих RP и coRP.

Класс п содержится в ЗПП, и некоторые компьютерные ученые предположили, что п = ЗПП, то есть каждый алгоритм Лас-Вегаса имеет детерминированный эквивалент полиномиального времени.

Существует оракул, относительно которого ЗПП = EXPTIME. Доказательство для ЗПП = EXPTIME означало бы, что пЗПП, в качестве пEXPTIME (видеть теорема об иерархии времени).

Смотрите также

внешняя ссылка