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