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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • PCP [O (log n ), O (1)] =  NP (теорема PCP)
  • PCP [poly ( n ), O (1)] =  PCP [poly ( n ), poly ( n )] =  NEXP (MIP = NEXP).

Также известно, что PCP [ r ( n ),  q ( n )] ⊆ NTIME (poly (n, 2 O ( r ( n )) q ( n ))). В частности, PCP [log n , poly ( n )] = NP . С другой стороны, если NP ⊆ PCP [o (log n ), o (log n )], то P = NP .

Линейный PCP

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

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

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

Внешние ссылки