Вероятностно проверяемое доказательство - Probabilistically checkable proof

В теория сложности вычислений, а вероятностно проверяемое доказательство (PCP) является разновидностью доказательство что можно проверить рандомизированный алгоритм используя ограниченную степень случайности и считывая ограниченное количество бит доказательства. Затем требуется, чтобы алгоритм принимал правильные доказательства и отклонял неправильные доказательства с очень высокой вероятностью. Стандартное доказательство (или свидетельство ), как используется в верификатор -основанное определение класс сложности НП, также удовлетворяет этим требованиям, поскольку процедура проверки детерминированно считывает все доказательство, всегда принимает правильные доказательства и отклоняет неправильные доказательства. Однако то, что делает их интересными, - это наличие вероятностно проверяемых доказательств, которые можно проверить, прочитав только несколько бит доказательства, используя случайность существенным образом.

Вероятностно проверяемые доказательства порождают множество классов сложности в зависимости от количества требуемых запросов и количества используемой случайности. Класс PCP[р(п),q(п)] относится к набору проблемы решения которые имеют вероятностно проверяемые доказательства, которые могут быть проверены за полиномиальное время, используя не более р(п) случайные биты и путем чтения не более q(п) кусочки доказательства.[1] Если не указано иное, правильные доказательства всегда должны приниматься, а неправильные доказательства должны отклоняться с вероятностью более 1/2. В Теорема PCP, главный результат в теории сложности вычислений, утверждает, что PCP[O (журнал п), O (1)] =НП.

Определение

Учитывая проблема решения L(или язык L с его алфавитным множеством Σ), a вероятностно проверяемая система доказательства за L с полнотой c(п) и надежность s(п), где 0 ≤ s(п) ≤ c(п) ≤ 1, состоит из доказывающего и проверяющего. Учитывая заявленное решение x с длиной n, которое может быть ложным, доказывающая сторона дает доказательство π в котором говорится Икс решает L (Икс ∈ L, доказательством является строка ∈ Σ*). И верификатор - это рандомизированный оракул машина Тьюринга V (в верификатор), который проверяет доказательство π за утверждение, что Икс решает L(или же Икс ∈ L) и решает, принимать ли заявление. Система обладает следующими свойствами:

  • Полнота: Для любого Икс ∈ L, учитывая доказательство π произведенный доказывающим системой, проверяющий принимает утверждение с вероятностью не менее c(п),
  • Разумность: Для любого Икс ∉ L, то для любого доказательства π, верификатор ошибочно принимает утверждение с вероятностью не более s(п).

Для вычислительная сложность верификатора, имеем сложность случайности р(п) для измерения максимального количества случайных битов, которые V использует во всех Икс длины п и сложность запроса q(п) верификатора - максимальное количество запросов, которые V делает к π по всем Икс длины п.

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

Утверждается, что верификатор неадаптивный если он выполняет все свои запросы до того, как получит какие-либо ответы на предыдущие запросы.

Класс сложности PCPc(п), s(п)[р(п), q(п)] - класс всех решающих задач, имеющих вероятностно проверяемые системы доказательств над двоичным алфавитом полноты. c(п) и надежность s(п), где верификатор неадаптивный, работает за полиномиальное время и имеет сложность случайности р(п) и сложность запроса q(п).

Сокращенное обозначение PCP[р(п), q(п)] иногда используется для PCP1, ½[р(п), q(п)]. Класс сложности PCP определяется как PCP1, ½[O (журналп), O (1)].

История и значение

Теория вероятностно проверяемых доказательств изучает мощность систем вероятностно проверяемых доказательств при различных ограничениях параметров (полнота, надежность, сложность случайности, сложность запроса и размер алфавита). Он имеет приложения для вычислительная сложность (особенно твердость приближения ) и криптография.

Определение вероятностно проверяемого доказательства было явно введено Аророй и Сафрой в 1992 г.[2] хотя их свойства были изучены ранее. В 1990 году Бабай, Фортноу и Лунд доказали, что PCP[поли(п), поли (п)] = NEXP, обеспечивающую первую нетривиальную эквивалентность стандартных доказательств (NEXP) и вероятностно проверяемые доказательства.[3] В Теорема PCP доказано в 1992 году, утверждает, что PCP[O (журнал п), O (1)] =НП.[2][4]

Теория твердость приближения требует детального понимания роли полноты, правильности, размера алфавита и сложности запроса в вероятностно проверяемых доказательствах.

Характеристики

С точки зрения вычислительной сложности, для экстремальных значений параметров определение вероятностно проверяемых доказательств, как легко видеть, эквивалентно стандартному. классы сложности. Например, у нас есть следующие настройки для разных настроек PCP[r (n), q (n)]:

  • PCP[0, 0] = п (п определяется как отсутствие случайности и доступа к доказательству.)
  • PCP[O (журнал (п)), 0] = п (Логарифмическое число случайных битов не помогает машине Тьюринга с полиномиальным временем, поскольку она может попробовать все возможные случайные строки логарифмической длины за полиномиальное время.)
  • PCP[0, O (журнал (п))] = п (Без случайности доказательство можно представить себе как строку фиксированного логарифмического размера. Полиномиальная машина времени может опробовать все возможные доказательства логарифмического размера за полиномиальное время.)
  • PCP[поли(п), 0] = coRP (По определению coRP.)
  • PCP[0, поли (п)] = НП (По определению NP, основанному на верификаторе.)

Теорема PCP и MIP = NEXP можно охарактеризовать следующим образом:

  • PCP[O (журнал п), O (1)] =НП (теорема PCP)
  • PCP[поли(п), O (1)] =PCP[поли(п),поли(п)] = NEXP (MIP = NEXP).

Также известно, что PCP[р(п), q(п)] ⊆ NTIME (поли (п, 2O (р(п))q(п))). Особенно, PCP[бревно п, поли (п)] = НП. С другой стороны, если НП ⊆ PCP[o (журнал п), o (журнал п)] тогда P = NP.[2]

Линейный PCP

Линейный PCP - такой, что по запросу q оракул выполняет только линейную операцию над доказательством. . То есть ответ оракула на запрос q является линейной функцией .

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

Рекомендации

  1. ^ Арора, Санджив; Варак, Вооз (2007), Вычислительная сложность: современный подход, Издательство Кембриджского университета, п. 241, ISBN  978-0-521-42426-4
  2. ^ а б c Арора, Санджив; Сафра, Шмуэль (1998), "Вероятностная проверка доказательств: новая характеристика NP", Журнал ACM, 45 (1): 70–122, Дои:10.1145/273865.273901
  3. ^ Бабай, Ласло; Фортноу, Лэнс; Лунд, Карстен (1990), «Недетерминированное экспоненциальное время имеет интерактивные протоколы с двумя проверяющими», Материалы 31-го ежегодного симпозиума по основам компьютерных наук (FOCS 1990), стр. 16–25, CiteSeerX  10.1.1.130.9311, Дои:10.1109 / FSCS.1990.89520, ISBN  978-0-8186-2082-9
  4. ^ Арора, Санджив; Лунд, Карстен; Мотвани, Раджив; Судан, Мадху; Сегеди, Марио (1998), "Проверка доказательства и трудность аппроксимационных задач", Журнал ACM, 45 (3): 501–555, Дои:10.1145/278298.278306

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