WikiDer > ЗПП (сложность)
 | Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. (Январь 2013) (Узнайте, как и когда удалить этот шаблон сообщения) |
В теория сложности, ЗПП (вероятностный полиномиальное время) это класс сложности проблем, для которых вероятностная машина Тьюринга существует с этими свойствами:
- Он всегда возвращает правильный ответ ДА или НЕТ.
- Время работы полиномиально от ожидания для каждого ввода.
Другими словами, если алгоритму разрешено подбрасывать действительно случайную монету во время его работы, он всегда будет возвращать правильный ответ, а в случае проблемы с размером п, есть полином п(п) так, что среднее время работы будет меньше п(п), хотя иногда может быть намного дольше. Такой алгоритм называется Алгоритм Лас-Вегаса.
В качестве альтернативы, ЗПП можно определить как класс задач, для которых вероятностная машина Тьюринга существует с этими свойствами:
- Он всегда выполняется за полиномиальное время.
- Он возвращает ответ ДА, НЕТ или НЕ ЗНАЮ.
- Ответ всегда либо НЕ ЗНАЮ, либо правильный ответ.
- Он возвращает НЕ ЗНАЮ с вероятностью не более 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 содержится в ЗППНП.
Подключение к другим классам
С ЗПП = RP ∩ coRP, ЗПП очевидно содержится в обоих RP и coRP.
Класс п содержится в ЗПП, и некоторые компьютерные ученые предположили, что п = ЗПП, то есть каждый алгоритм Лас-Вегаса имеет детерминированный эквивалент полиномиального времени.
Существует оракул, относительно которого ЗПП = EXPTIME. Доказательство для ЗПП = EXPTIME означало бы, что п ≠ ЗПП, в качестве п ≠ EXPTIME (видеть теорема об иерархии времени).