ЗПП (сложность) - ZPP (complexity)
В теории сложности , ЗПП (нулевой ошибки вероятностный полином времени ) является классом сложности задач , для которых вероятностная машина Тьюринга существует с этими свойствами:
- Он всегда возвращает правильный ответ ДА или НЕТ.
- Время выполнения полиномиально от ожидания для каждого ввода.
Другими словами, если алгоритму разрешено подбрасывать по-настоящему случайную монету во время его работы, он всегда будет возвращать правильный ответ, а для задачи размера n существует некоторый многочлен p ( n ), такой что среднее бегущее time будет меньше p ( n ), хотя иногда может быть намного больше. Такой алгоритм называется алгоритмом Лас-Вегаса .
В качестве альтернативы ZPP можно определить как класс задач, для которых существует вероятностная машина Тьюринга со следующими свойствами:
- Он всегда выполняется за полиномиальное время.
- Он возвращает ответ ДА, НЕТ или НЕ ЗНАЮ.
- Ответ всегда либо НЕ ЗНАЮ, либо правильный ответ.
- Он возвращает НЕ ЗНАЮ с вероятностью не более 1/2 для каждого ввода (в противном случае - правильный ответ).
Эти два определения эквивалентны.
Определение ZPP основано на вероятностных машинах Тьюринга, но для ясности отметим, что другие классы сложности, основанные на них, включают BPP и RP . Класс BQP основан на другой машине со случайностью: квантовом компьютере .
Определение пересечения
Класс ZPP в точности совпадает с пересечением классов RP и co-RP . Это часто считается определением ZPP . Чтобы показать это, сначала обратите внимание, что каждая проблема, которая есть как в RP, так и в co-RP, имеет следующий алгоритм Лас-Вегаса :
- Предположим, у нас есть язык L, распознаваемый как алгоритмом RP A, так и (возможно, совершенно другим) алгоритмом co-RP B.
- Учитывая ввод, запустите A на входе для одного шага. Если он возвращает ДА, ответ должен быть ДА. В противном случае запустите B на входе для одного шага. Если он возвращает НЕТ, ответ должен быть НЕТ. Если ничего не происходит, повторите этот шаг.
Обратите внимание, что только одна машина может дать неправильный ответ, и вероятность того, что эта машина даст неправильный ответ во время каждого повторения, составляет не более 50%. Это означает, что шанс достижения k- го раунда экспоненциально уменьшается в k , показывая, что ожидаемое время выполнения является полиномиальным. Это показывает, что пересекающиеся RP co-RP содержится в ZPP .
Для того, чтобы показать , что ЗПП содержится в РП пересекаются со-RP , предположим , что мы имеем Лас - Вегас алгоритм C , чтобы решить проблему. Затем мы можем построить следующий алгоритм RP :
- Запустите C как минимум в два раза больше ожидаемого времени работы. Если он дает ответ, дайте этот ответ. Если он не дает ответа до того, как мы его остановим, дайте НЕТ.
Согласно неравенству Маркова , вероятность того, что он даст ответ до того, как мы его остановим, составляет не менее 1/2. Это означает, что вероятность того, что мы дадим неправильный ответ в случае ДА, остановившись и получив НЕТ, составляет не более 1/2, что соответствует определению алгоритма RP . Совместно RP алгоритм идентичен, за исключением того, что она дает ДА , если С «раз из».
Свидетели и доказательства
Классы NP , RP и ZPP можно рассматривать с точки зрения доказательства принадлежности к множеству.
Определение: Верификатор V для множества Х представляет собой машину Тьюринга таким образом, что:
- если x находится в X, тогда существует строка w такая, что V ( x , w ) принимает;
- если й не в X , то для всех строк ш , V ( х , ш ) отклоняет.
Строку w можно рассматривать как доказательство членства. В случае коротких доказательств (длина которых ограничена полиномом от размера входных данных), которые могут быть эффективно проверены ( V - детерминированная машина Тьюринга с полиномиальным временем), строка w называется свидетелем .
Ноты:
- Определение очень асимметричное. Доказательство того, что x находится в X, - это одна строка. Доказательство того, что x не принадлежит X, - это набор всех строк, ни одна из которых не является доказательством принадлежности.
- Доступность свидетеля одинакова. Для всех x в X должен быть свидетель. Это не тот случай, когда некоторые x в X слишком сложно проверить, а большинство - нет.
- Свидетель не обязательно должен быть традиционным доказательством. Если V - вероятностная машина Тьюринга, которая, возможно, могла бы принять x, если x находится в X, то доказательством является цепочка подбрасываний монеты, которая приводит машину, благодаря удаче, интуиции или гениальности, к принятию x .
- Совместная концепция - это доказательство непринадлежности или принадлежности к набору дополнений.
Классы NP , RP и ZPP являются наборами, у которых есть свидетели членства. Класс NP требует только наличия свидетелей. Они могут быть очень редкими. Из 2 возможных строк f (| x |) , где f - многочлен, только одна должна заставить верификатор принять (если x находится в X. Если x не в X, никакая строка не заставит верификатор принять).
Для классов RP и ZPP любая случайно выбранная строка, скорее всего, будет свидетелем.
Соответствующие классы имеют свидетельство о неприсоединении. В частности, co-RP - это класс множеств, для которых, если x не входит в X, любая случайно выбранная строка может свидетельствовать о непринадлежности. ZPP - это класс наборов, для которых любая случайная строка может быть свидетелем x в X или x не в X, в зависимости от обстоятельств.
Связать это определение с другими определениями RP , co-RP и ZPP несложно. Вероятностная машина Тьюринга V * w ( x ) с полиномиальным временем соответствует детерминированной машине Тьюринга V ( x , w ) с полиномиальным временем путем замены случайной ленты V * второй входной лентой для V, на которой записана последовательность монета подбрасывает. Выбирая свидетеля в качестве случайной строки, верификатор представляет собой вероятностную машину Тьюринга с полиномиальным временем, чья вероятность принятия x, когда x находится в X , велика (скажем, больше 1/2), но равна нулю, если x ∉ X (для RP ); отклонения x, когда x не в X, велико, но равно нулю, если x ∈ X (для co-RP ); и правильного принятия или отклонения x как члена X велико, но ноль неправильного принятия или отклонения x (для ZPP ).
Путем повторного случайного выбора возможного свидетеля большая вероятность того, что случайная строка является свидетелем, дает алгоритм ожидаемого полиномиального времени для принятия или отклонения ввода. И наоборот, если ожидается, что машина Тьюринга будет работать за полиномиальное время (для любого заданного x), тогда значительная часть прогонов должна быть ограничена полиномиальным временем, и последовательность монет, используемая в таком прогоне, будет свидетелем.
ЗПП следует противопоставлять БПП . Класс BPP не требует свидетелей, хотя свидетелей достаточно (следовательно, BPP содержит RP , co-RP и ZPP ). БПП язык имеет V (х, ш) принимает на (очистить) большинства строк ж , если х в X, и , наоборот , отвергают на (очистить) большинства строк ж , если й не в X . Никакая отдельная строка w не должна быть окончательной, и поэтому они, как правило, не могут считаться доказательствами или свидетелями.
Теоретико-сложные свойства
Известно, что ZPP замкнута относительно дополнения; то есть ZPP = co-ZPP.
ZPP сам по себе низкий , а это означает, что машина ZPP, способная мгновенно решать проблемы ZPP (машина оракула ZPP), не более мощная, чем машина без этой дополнительной мощности. В символах ZPP ZPP = ZPP .
ЗПП НП БПП = ЗПП НП .
NP BPP содержится в ZPP НП .
Подключение к другим классам
Поскольку ZPP = RP ∩ coRP , очевидно , что ZPP содержится как в RP, так и в coRP .
Класс P содержится в ZPP , и некоторые компьютерные ученые предположили, что P = ZPP , т. Е. Каждый алгоритм Лас-Вегаса имеет детерминированный эквивалент полиномиального времени.
Существует оракул, относительно которого ZPP = EXPTIME . Доказательство для ZPP = EXPTIME будет означать, что P ≠ ZPP , поскольку P ≠ EXPTIME (см. Теорему об иерархии времени ).