В теории вычислительной сложности вероятностно проверяемое доказательство ( 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 ≤ 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 .
В приведенном выше определении длина доказательства не упоминается, так как обычно она включает набор алфавитов и всех свидетелей. Для доказывающего нас не волнует, как он приходит к решению задачи; нас интересует только доказательство принадлежности решения к языку.
Верификатор считается неадаптивным , если он делает все свои запросы до того, как получит какие-либо ответы на предыдущие запросы.