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