Войти
В теории сложности вычислений вероятностно проверяемое доказательство (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), и решает, принять ли утверждение. Система обладает следующими свойствами:
Для вычислительной сложности верификатора мы иметь сложность случайности r (n) для измерения максимального количества случайных битов, которые V использует по всем x длины n, а сложность запроса q (n) проверяющего - это максимальное количество запросов, которые V делает к π по всем x длины n.
В приведенном выше определении объем доказательства не упоминается, поскольку обычно он включает алфавитный набор и всех свидетелей. Для доказывающего нас не волнует, как он придет к решению проблемы; мы заботимся только о том, что оно дает доказательство принадлежности решения языку.
Верификатор считается неадаптивным, если он выполняет все свои запросы до того, как получит какие-либо ответы на предыдущие запросы.
Класс сложности PCPc (n), s (n) [r (n), q (n)] - это класс всех задач решения, имеющих вероятностно проверяемые системы доказательств над двоичным алфавитом полноты c (n) и надежности s (n), где верификатор неадаптивен, работает за полиномиальное время и имеет сложность случайности r (n) и сложность запроса q (n).
Сокращенное обозначение PCP [r (n), q (n)] иногда используется для PCP1, ½ [r ( n), q (n)]. Класс сложности PCP определяется как PCP1, ½ [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 теоремы и MIP = NEXP можно охарактеризовать следующим образом:
Также известно, что PCP [r (n), q (n)] ⊆ NTIME (poly (n, 2q (n))). В частности, PCP [log n, poly (n)] = NP. С другой стороны, если NP⊆ PCP [o (log n), o (log n)], то P = NP.
Линейный PCP такой, что учитывая запрос q, оракул выполняет только линейную операцию с доказательством 
