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

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

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

Определение

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

Полнота : для любого $x \in L$ , учитывая доказательство π, произведенное доказывающим системы, проверяющий принимает утверждение с вероятностью не менее c ( n ),
Разумность : для любого $x \notin 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, 1/2 [r (n), q (n)]$ . Класс сложности PCP определяется как $PCP 1, 1/2 [O (log n), O (1)]$ .

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

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

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

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

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

С точки зрения вычислительной сложности, при экстремальных настройках параметров определение вероятностно проверяемых доказательств легко увидеть эквивалентным стандартным классам сложности . имеем следующее Например, для разных настроек 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, поли( n )] = NP (согласно определению NP на основе верификатора.)

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

$PCP [O (log n), O (1)] = NP$ (теорема PCP)
$PCP [поли(n), O (1)] = PCP [поли (n), поли (n)] = NEXP (MIP = NEXP)$ .

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

Линейный PCP

Линейная PCP - это PCP, в которой доказательством является вектор элементов конечного поля. $\pi \in \mathbb {F} ^{n}$ , и такой, что оракулу PCP разрешено выполнять только линейные операции при доказательстве. А именно, ответ оракула на запрос проверяющего $q\in \mathbb {F} ^{n}$ является линейной функцией $f(q,\pi )$ . Линейные PCP имеют важное применение в системах доказательств, которые могут быть скомпилированы в SNARK.

См. также

Интерактивные системы доказательств

Ссылки

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

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

Голографическое доказательство в Математической энциклопедии
Конспекты курса PCP Субхаша Хота в Нью-Йоркском университете , 2008 г.
Конспекты курса PCP и «История теоремы PCP», написанные Райаном О'Доннеллом и Венкатесаном Гурусвами из Вашингтонского университета , 2005 г.
Зоопарк сложности : PCP

[ab07-1] Арора, Санджив ; Барак, Боаз (2007), Вычислительная сложность: современный подход , Cambridge University Press , стр. 241, ISBN 978-0-521-42426-4

[as92-2] Перейти обратно: ^а ^б ^с Арора, Санджив ; Сафра, Шмуэль (1998), «Вероятностная проверка доказательств: новая характеристика NP», Журнал ACM , 45 (1): 70–122, doi : 10.1145/273865.273901 , S2CID 751563

[bfl90-3] Бабай, Ласло ; На данный момент, Лэнс ; Лунд, Карстен (1990), «Недетерминированное экспоненциальное время имеет интерактивные протоколы с двумя доказательствами», Труды 31-го ежегодного симпозиума по основам информатики (FOCS 1990) , стр. 16–25, CiteSeerX 10.1.1.130.9311 , doi : 10.1109/FSCS.1990.89520 , ISBN 978-0-8186-2082-9 , S2CID 38429596

[almss-4] Арора, Санджив ; Лунд, Карстен ; Мотвани, Раджив ; Судан, Мадху ; Сегеди, Марио (1998), «Проверка доказательств и сложность задач аппроксимации», Журнал ACM , 45 (3): 501–555, doi : 10.1145/278298.278306 , S2CID 8561542

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

v т и Классы сложности
Считается возможным	ВРЕМЯ ДЛОГА переменного тока ⁰ АСС ⁰ ТК ⁰ л СЛ РЛ Флорида Нидерланды NL-полный Северная Каролина СК СС П P-полный ЗПП РП БПП Министерство национальной обороны АПХ ФП
Подозрение неосуществимое	ВВЕРХ НАПРИМЕР NP-полный NP-жесткий со-НП со-NP-полный ТФНП ФНП ЯВЛЯЮСЬ КМА PH ⊕P ПП #П #P-полное ИП PSPACE PSPACE-полный
Считается невозможным	ВРЕМЯ ЭКСПРЕСС СЛЕДУЮЩЕЕ ВРЕМЯ EXPSPACE 2-ВРЕМЯ ЭКСПЛУАТАЦИИ ЭЛЕМЕНТАРНЫЙ пиар Р РЭ ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерарх Гжегорчик Арифметическая иерархия Булева иерархия
Семьи классов	DTIME NTIME ДСПЕЙС НСПАСЕ Вероятностно проверяемое доказательство Интерактивная система доказательств
Список классов сложности