IP (сложность) - IP (complexity)

В теории сложности вычислений класс IP (который означает «Интерактивное полиномиальное время») - это класс задач, решаемых с помощью интерактивной системы доказательства . Равен классу PSPACE . Результат был закреплен в серии статей: первая, написанная Лундом, Карлоффом, Фортноу и Нисаном, показала, что co-NP имеет несколько интерактивных доказательств с помощью доказывающих устройств; а второй, Шамир, использовал свою технику, чтобы установить, что IP = PSPACE. В результате получился известный пример, когда доказательство не релятивизирует .

Концепция интерактивной системы доказательства была впервые представлена Шафи Голдвассером , Сильвио Микали и Чарльзом Ракоффом в 1985 году. Интерактивная система доказательства состоит из двух машин, доказывающего P , который представляет доказательство того, что данная строка n является членом некоторый язык и верификатор V , который проверяет правильность представленного доказательства. Предполагается, что доказывающая сторона бесконечна в вычислениях и хранении, в то время как верификатор представляет собой вероятностную машину полиномиального времени с доступом к случайной битовой строке, длина которой полиномиальна от размера n . Эти две машины обмениваются полиномиальным числом сообщений p ( n ), и после завершения взаимодействия проверяющий должен решить, присутствует ли n на языке, с вероятностью ошибки только 1/3. (Таким образом, любой язык в BPP находится в IP , с тех пор проверяющий может просто проигнорировать доказывающего и принять решение самостоятельно.)

Определение

Язык L принадлежит IP, если существуют V , P такие, что для всех Q , w :

${\ displaystyle w \ in L \ Rightarrow \ Pr [V \ leftrightarrow P {\ text {принимает}} w] \ geq {\ tfrac {2} {3}}}$

${\ displaystyle w \ not \ in L \ Rightarrow \ Pr [V \ leftrightarrow Q {\ text {accept}} w] \ leq {\ tfrac {1} {3}}}$

Протокол Артура – ​​Мерлина , введенный Ласло Бабаем , аналогичен по своей природе, за исключением того, что количество раундов взаимодействия ограничено константой, а не полиномом.

Goldwasser et al. показали, что протоколы публичных монет , в которых случайные числа, используемые верификатором, предоставляются доказывающему вместе с задачами, не менее мощны, чем протоколы приватных монет. Для воспроизведения эффекта протокола частной монеты требуется не более двух дополнительных раундов взаимодействия. Противоположное включение является простым, потому что проверяющий всегда может отправить проверяющему результаты своих частных подбрасываний монет, что доказывает, что два типа протоколов эквивалентны.

В следующем разделе мы докажем, что IP = PSPACE , важная теорема вычислительной сложности, которая демонстрирует, что интерактивная система доказательства может использоваться для определения того, является ли строка членом языка за полиномиальное время, даже если традиционное доказательство PSPACE может быть экспоненциально длинным.

Подтверждение IP = PSPACE

Доказательство можно разделить на две части: мы покажем, что IP ⊆ PSPACE и PSPACE ⊆ IP .

IP ⊆ PSPACE

Чтобы продемонстрировать, что IP ⊆ PSPACE , мы представляем имитацию интерактивной системы доказательства с помощью машины полиномиального пространства. Теперь мы можем определить:

${\ displaystyle \ Pr [V {\ text {принимает}} w {\ text {, начиная с}} M_ {j}] = \ max \ nolimits _ {P} \ Pr \ left [V \ leftrightarrow P {\ text { принимает}} w {\ text {начиная с}} M_ {j} \ right]}$

и для каждого 0 ≤ j ≤ p и каждой истории сообщений M _j мы индуктивно определяем функцию N _{M j} :

${\ displaystyle N_ {M_ {j}} = {\ begin {cases} 0 & j = p {\ text {and}} m_ {p} = {\ text {reject}} \\ 1 & j = p {\ text {and} } m_ {p} = {\ text {accept}} \\\ max _ {m_ {j + 1}} N_ {M_ {j + 1}} & j <p {\ text {and}} j {\ text { нечетно}} \\ {\ text {wt-avg}} _ {m_ {j + 1}} N_ {M_ {j + 1}} & j <p {\ text {and}} j {\ text {четно }} \\\ конец {случаи}}}$

куда:

${\ displaystyle {\ text {wt-avg}} _ {m_ {j + 1}} N_ {M_ {j + 1}}: = \ sum \ nolimits _ {m_ {j + 1}} \ Pr \ nolimits _ {r} [V (w, r, M_ {j}) = m_ {j + 1}] N_ {M_ {j + 1}}}$

где Pr _r - вероятность, взятая по случайной строке r длины p . Это выражение представляет собой среднее значение N _{M j + 1} , взвешенное по вероятности того, что проверяющий отправил сообщение m _{j + 1} .

Возьмем M ₀ в качестве пустой последовательности сообщений, здесь мы покажем, что N _{M 0} может быть вычислено в полиномиальном пространстве, и что N _{M 0} = Pr [ V принимает w ]. Во-первых, чтобы вычислить N _{M 0} , алгоритм может рекурсивно вычислить значения N _{M j} для каждого j и M _j . Поскольку глубина рекурсии равна p , необходимо только полиномиальное пространство. Второе требование состоит в том, что нам нужно N _{M 0} = Pr [ V принимает w ], значение, необходимое для определения того, входит ли w в A. Мы используем индукцию, чтобы доказать это следующим образом.

Мы должны показать, что для любого 0 ≤ j ≤ p и любого M _j , N _{M j} = Pr [ V принимает w, начиная с M _j ], и мы сделаем это, используя индукцию по j . Базовый случай - доказать для j = p . Затем мы воспользуемся индукцией, чтобы перейти от p к 0.

Базовый случай j = p довольно прост. Поскольку m _p принимает или отклоняет, если m _p принимает, N _{M p} определяется как 1, а Pr [ V принимает w, начиная с M _j ] = 1, поскольку поток сообщений указывает принятие, таким образом, утверждение истинно. Если m _p отклонено, аргумент очень похож.

Для индуктивной гипотезы мы предполагаем, что для некоторого j +1 ≤ p и любой последовательности сообщений M _{j + 1} , N _{M j + 1} = Pr [ V принимает w, начиная с M _{j + 1} ], а затем докажем гипотезу для j и любая последовательность сообщений M _j .

Если J четно, т _{J + 1} является сообщение от V к Р . По определению N _{M j} ,

${\ Displaystyle N_ {M_ {j}} = \ sum \ nolimits _ {m_ {j + 1}} \ Pr \ nolimits _ {r} \ left [V (w, r, M_ {j}) = m_ {j +1} \ right] N_ {M_ {j + 1}}.}$

Тогда по предположению индукции мы можем сказать, что это равно

${\ displaystyle \ sum \ nolimits _ {m_ {j + 1}} \ Pr \ nolimits _ {r} \ left [V (w, r, M_ {j}) = m_ {j + 1} \ right] * \ Pr \ left [V {\ text {принимает}} w {\ text {, начиная с}} M_ {j + 1} \ right].}$

Наконец, по определению мы видим, что это равно Pr [ V принимает w, начиная с M _j ].

Если J нечетно, т _{J + 1} является сообщение от P до V . По определению,

${\ displaystyle N_ {M_ {j}} = \ max \ nolimits _ {m_ {j + 1}} N_ {M_ {j + 1}}.}$

Тогда по предположению индукции это равно

${\ displaystyle \ max \ nolimits _ {m_ {j + 1}} * \ Pr [V {\ text {принимает}} w {\ text {, начиная с}} M_ {j + 1}].}$

Это равно Pr [ V принимает w, начиная с M _j ], поскольку:

${\ displaystyle \ max \ nolimits _ {m_ {j + 1}} \ Pr [V {\ text {принимает}} w {\ text {, начиная с}} M_ {j + 1}] \ leq \ Pr [V { \ text {принимает w, начиная с}} M_ {j}]}$

потому что доказывающий с правой стороны может отправить сообщение m _{j + 1,} чтобы максимизировать выражение с левой стороны. А также:

${\ displaystyle \ max \ nolimits _ {m_ {j + 1}} \ Pr \ left [V {\ text {принимает}} w {\ text {, начиная с}} M_ {j + 1} \ right] \ geq \ Pr \ left [V {\ text {принимает}} w {\ text {, начиная с}} M_ {j} \ right]}$

Поскольку один и тот же Прувер не может сделать ничего лучше, чем отправить то же сообщение. Таким образом, это верно независимо от того, четно или нечетно i, и доказательство того, что IP ⊆ PSPACE , завершено.

Здесь мы построили полиномиальное пространство машины , которая использует лучший Доказывающий P для конкретной строки ш в языке А . Мы используем эту лучшую доказывающую программу вместо доказывающей со случайными входными битами, потому что мы можем опробовать каждый набор случайных входных битов в полиномиальном пространстве. Поскольку мы смоделировали интерактивную систему доказательства с помощью машины с полиномиальным пространством, мы показали, что IP ⊆ PSPACE , как и требовалось.

PSPACE ⊆ IP

Чтобы проиллюстрировать технику, которая будет использоваться для доказательства PSPACE ⊆ IP , мы сначала докажем более слабую теорему, которая была доказана Лундом и др.: #SAT ∈ IP . Затем, используя концепции этого доказательства, мы расширим его, чтобы показать, что TQBF ∈ IP . Поскольку TQBF ∈ PSPACE -полный и TQBF ∈ IP, то PSPACE ⊆ IP .

#SAT является членом IP

Начнем с того, что покажем, что #SAT находится в IP , где:

${\ displaystyle \ # {\ text {SAT}} = \ left \ {\ langle \ varphi, k \ rangle \: \ \ varphi {\ text {- формула CNF с точно}} k {\ text {, удовлетворяющими присваиваниям }}\Правильно\}.}$

Обратите внимание, что это отличается от обычного определения #SAT тем , что это проблема решения, а не функция.

Сначала мы используем арифметизацию, чтобы отобразить булеву формулу с n переменными, φ ( b ₁ , ..., b _n ) в многочлен p _φ ( x ₁ , ..., x _n ), где p _φ имитирует φ в этом p _φ равно 1, если φ истинно, и 0 в противном случае, если переменным p _φ присвоены логические значения. Булевы операции ∨, ∧ и ¬, используемые в φ, моделируются в p _φ путем замены операторов в φ, как показано в таблице ниже.

Правила арифметизации для преобразования булевой формулы φ ( b ₁ , ..., b _n ) в полином p _φ ( x ₁ , ..., x _n )

а ∧ б	ab
а ∨ б	a ∗ b  : = 1 - (1 - a ) (1 - b )
¬ а	1 - а

Например, φ = a ∧ ( b ∨ ¬ c ) можно преобразовать в полином следующим образом:

${\ Displaystyle {\ begin {align} p _ {\ varphi} & = a \ wedge (b \ vee \ neg c) \\ & = a \ wedge \ left (b * (1-c) \ right) \\ & = a \ клин \ left (1- (1-b) (1- (1-c)) \ right) \\ & = a \ left (1- (1-b) (1- (1-c)) \ right) \\ & = a- (ac-abc) \ end {выравнивается}}}$

Каждая из операций ab и a ∗ b приводит к многочлену со степенью, ограниченной суммой степеней многочленов для a и b, и, следовательно, степень любой переменной не больше длины φ.

Пусть теперь F - конечное поле порядка q > 2 ⁿ ; также требуйте, чтобы q было не менее 1000. Для каждого 0 ≤ i ≤ n определите функцию f _i на F , имеющую параметры , и единственную переменную a _i в F : для 0 ≤ i ≤ n и для let ${\ displaystyle a_ {1}, \ dots, a_ {i-1} \ in F}$${\ displaystyle a_ {1}, \ dots, a_ {i} \ in F}$

${\ displaystyle f_ {i} (a_ {1}, \ dots, a_ {i}) = \ sum \ nolimits _ {a_ {i + 1}, \ dots, a_ {n} \ in \ {0,1 \ }} p (a_ {1}, \ dots, a_ {n}).}$

Обратите внимание, что значение f ₀ - это количество удовлетворяющих присвоений φ. f ₀ - это функция void без переменных.

Теперь протокол для #SAT работает следующим образом:

• Фаза 0 : Прувер Р выбирает простой д > 2 ^п и вычисляет F ₀ , затем он посылает д и е ₀ до верификатора V . V проверяет, что q является простым числом больше max (1000, 2 ⁿ ) и что f ₀ () = k .
• Фаза 1 : P отправляет коэффициенты f ₁ ( z ) как полином от z. V проверяет, что степень f ₁ меньше n и что f ₀ = f ₁ (0) + f ₁ (1). (Если не V отвергает). В теперь посылает случайное число R ₁ от F до P .
• Фаза i : P отправляет коэффициенты в виде полинома от z . V проверяет, что степень f _i меньше n и что . (Если не V отвергает). В теперь посылает случайное число г _я от F до P .${\ displaystyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, z)}$${\ displaystyle f_ {i-1} (r_ {1}, \ dots, r_ {i-1}) = f_ {i} (r_ {1}, \ dots, r_ {i-1}, 0) + f_ {i} (r_ {1}, \ dots, r_ {i-1}, 1)}$
• Фаза п + 1 : V оценивает , чтобы сравнить со значением . Если они равны, V принимает, иначе V отклоняет.${\ displaystyle p (r_ {1}, \ dots, r_ {n})}$${\ displaystyle f_ {n} (r_ {1}, \ dots, r_ {n})}$

Обратите внимание, что это алгоритм публичных монет.

Если φ имеет k удовлетворяющих назначений, очевидно, что V примет. Если φ не имеет k удовлетворяющих назначений, мы предполагаем, что существует доказывающий, который пытается убедить V, что φ действительно имеет k удовлетворяющих назначений. Мы показываем, что это возможно только с малой вероятностью. ${\ displaystyle {\ tilde {P}}}$

Для того, чтобы предотвратить V от отказа в фазе 0, должен послать неправильное значение для P . Затем на этапе 1 необходимо отправить неверный многочлен со свойством, что . Когда V выбирает случайный r ₁ для отправки в P , ${\ displaystyle {\ tilde {P}}}$${\ displaystyle {\ tilde {f}} _ {0} ()}$${\ displaystyle {\ tilde {P}}}$${\ displaystyle {\ tilde {f}} _ {1}}$${\ displaystyle {\ tilde {f}} _ {1} (0) + {\ tilde {f}} _ {1} (1) = {\ tilde {f}} _ {0} ()}$

${\ Displaystyle \ Pr \ left [{\ тильда {f}} _ {1} (r_ {1}) = f_ {1} (r_ {1}) \ right] <{\ tfrac {1} {n ^ { 2}}}.}$

Это связано с тем, что многочлен от одной переменной степени не выше d может иметь не более d корней (если он всегда не равен 0). Таким образом, любые два полинома от одной переменной степени не выше d могут быть равны только в d местах. Поскольку | F | > 2 ⁿ вероятность того, что r ₁ будет одним из этих значений, не больше, если n > 10, или не больше ( n / 1000) ≤ ( n / n ³ ), если n ≤ 10. ${\ Displaystyle п / 2 ^ {п} <п / п ^ {3}}$

Обобщая эту идею для других фаз, мы имеем для каждого 1 ≤ i ≤ n, если

${\ displaystyle {\ tilde {f}} _ {i-1} (r_ {1}, \ dots, r_ {i-1}) \ neq f_ {i-1} (r_ {1}, \ dots, r_ {i-1}),}$

тогда для r _i, выбранного случайным образом из F ,

${\ displaystyle \ Pr \ left [{\ тильда {f}} (r_ {1}, \ dots, r_ {i}) = f_ {i} (r_ {1}, \ dots, r_ {i}) \ right ] \ leq {\ tfrac {1} {n ^ {2}}}.}$

Есть n фаз, поэтому вероятность того, что повезет, потому что V выберет на каком-то этапе удобное r _i , не превышает 1 / n . Таким образом, ни один доказывающий не может заставить проверяющего принять с вероятностью больше 1 / n . Мы также можем видеть из определения, что верификатор V работает за вероятностное полиномиальное время. Таким образом, #SAT ∈ IP . ${\ displaystyle {\ tilde {P}}}$

TQBF является членом IP

Чтобы показать, что PSPACE - это подмножество IP , нам нужно выбрать проблему PSPACE-complete и показать, что она находится в IP . Как только мы это покажем, станет ясно, что PSPACE ⊆ IP . Продемонстрированная здесь техника доказательства принадлежит Ади Шамиру .

Мы знаем, что TQBF находится в PSPACE-Complete . Итак, пусть ψ будет количественным логическим выражением:

${\ displaystyle \ psi = {\ mathsf {Q}} _ {1} x_ {1} \ dots {\ mathsf {Q}} _ {m} x_ {m} [\ varphi]}$

где φ - формула КНФ. Тогда Q _i является квантором либо, либо ∀. Теперь f _i то же, что и в предыдущем доказательстве, но теперь оно также включает кванторы.

${\ displaystyle f_ {i} (a_ {1}, \ dots, a_ {i}) = {\ begin {cases} f_ {i} (a_ {1}, \ dots, a_ {m}) = 1 & {\ mathsf {Q}} _ {i + 1} x_ {i + 1} \ dots {\ mathsf {Q}} _ {m} x_ {m} [\ varphi (a_ {1}, \ dots, a_ {i} )] {\ text {истинно}} \\ 0 & {\ text {иначе}} \ end {case}}}$

Здесь φ ( a ₁ , ..., a _i ) - это φ с заменой от ₁ до a _i на x ₁ на x _i . Таким образом, f ₀ является истинным значением ψ. Чтобы арифметизировать ψ, мы должны использовать следующие правила:

${\ displaystyle f_ {i} (a_ {1}, \ dots, a_ {i}) = {\ begin {cases} f_ {i + 1} (a_ {1}, \ dots, a_ {i}, 0) \ cdot f_ {i + 1} (a_ {1}, \ dots, a_ {i}, 1) & {\ mathsf {Q}} _ {i + 1} = \ forall \\ f_ {i + 1} ( a_ {1}, \ dots, a_ {i}, 0) * f_ {i + 1} (a_ {1}, \ dots, a_ {i}, 1) & {\ mathsf {Q}} _ {i + 1} = \ существует \ end {case}}}$

где, как и ранее, мы определяем x ∗ y = 1 - (1 -  x ) (1 -  y ).

Используя метод, описанный в #SAT, мы должны столкнуться с проблемой, заключающейся в том, что для любого f _i степень результирующего многочлена может удваиваться с каждым квантором. Чтобы предотвратить это, мы должны ввести новый оператор сокращения R, который будет уменьшать степени полинома без изменения их поведения на логических входах.

Итак, теперь, прежде чем арифметизировать, мы вводим новое выражение: ${\ displaystyle \ psi = {\ mathsf {Q}} _ {1} x_ {1} \ dots {\ mathsf {Q}} _ {m} x_ {m} [\ varphi]}$

${\ displaystyle \ psi '= {\ mathsf {Q}} _ {1} \ mathrm {R} x_ {1} {\ mathsf {Q}} _ {2} \ mathrm {R} x_ {1} \ mathrm { R} x_ {2} \ dots {\ mathsf {Q}} _ {m} \ mathrm {R} x_ {1} \ dots \ mathrm {R} x_ {m} [\ varphi]}$

или по-другому:

${\ displaystyle \ psi '= {\ mathsf {S}} _ {1} y_ {1} \ dots {\ mathsf {S}} _ {k} y_ {k} [\ varphi], \ qquad {\ text { где}} {\ mathsf {S}} _ {i} \ in \ {\ forall, \ exists, \ mathrm {R} \}, \ y_ {i} \ in \ {x_ {1}, \ dots, x_ {м} \}}$

Теперь для каждого i ≤ k определим функцию f _i . Мы также определяем многочлен p ( x ₁ , ..., x _m ), который получается арифметизацией φ. Теперь, чтобы сохранить степень полинома низкой, мы определим f _i через f _{i + 1} : ${\ displaystyle f_ {k} (x_ {1}, \ dots, x_ {m})}$

${\ displaystyle {\ text {If}} {\ mathsf {S}} _ {i + 1} = \ forall, \ quad f_ {i} (a_ {1}, \ dots, a_ {i}) = f_ { i + 1} (a_ {1}, \ dots, a_ {i}, 0) \ cdot f_ {i + 1} (a_ {1}, \ dots, a_ {i}, 1)}$

${\ displaystyle {\ text {If}} {\ mathsf {S}} _ {i + 1} = \ exists, \ quad f_ {i} (a_ {1}, \ dots, a_ {i}) = f_ { i + 1} (a_ {1}, \ dots, a_ {i}, 0) * f_ {i + 1} (a_ {1}, \ dots, a_ {i}, 1)}$

${\ displaystyle {\ text {If}} {\ mathsf {S}} _ {i + 1} = \ mathrm {R}, \ quad f_ {i} (a_ {1}, \ dots, a_ {i}, a) = (1-a) f_ {i + 1} (a_ {1}, \ dots, a_ {i}, 0) + af_ {i + 1} (a_ {1}, \ dots, a_ {i} , 1)}$

Теперь мы видим, что операция редукции R не меняет степени многочлена. Также важно видеть, что операция R _x не изменяет значение функции на логических входах. Таким образом, f ₀ по-прежнему является значением истинности ψ, но значение R _x дает результат, линейный по x . Также после любого мы добавляем ψ ′, чтобы уменьшить степень до 1 после арифметизации . ${\ displaystyle {\ mathsf {Q}} _ {i} x_ {i}}$${\ Displaystyle \ mathrm {R} _ {x_ {1}} \ dots \ mathrm {R} _ {x_ {i}}}$${\ displaystyle {\ mathsf {Q}} _ {i}}$

Теперь опишем протокол. Если n - длина ψ, все арифметические операции в протоколе выполняются над полем размером не менее n ^4, где n - длина ψ.

• Фаза 0 : P → V : Р посылает F ₀ до V . V проверяет, что f ₀ = 1, и отклоняет, если нет.
• Фаза 1 : P → V : Р посылает F ₁ ( г ) до V . V использует коэффициенты для оценки f ₁ (0) и f ₁ (1). Затем он проверяет, что степень многочлена не превосходит n и выполняются следующие тождества:

${\ displaystyle f_ {0} (\ varnothing) = {\ begin {cases} f_ {1} (0) \ cdot f_ {1} (1) & {\ text {if}} {\ mathsf {S}} = \ forall \\ f_ {1} (0) * f_ {1} (1) & {\ text {if}} {\ mathsf {S}} = \ exists. \\ (1-r) f_ {1} ( 0) + rf_ {1} (1) & {\ text {if}} {\ mathsf {S}} = \ mathrm {R}. \ End {cases}}}$

Если что-то не удается, откажитесь.

• Фаза i : P → V : P пересылается как полином от z . r ₁ обозначает ранее установленные случайные значения для${\ displaystyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, z)}$${\ displaystyle r_ {1}, \ dots, r_ {i-1}}$

V использует коэффициенты для оценки и . Затем он проверяет, что степень полинома не превосходит n и что выполняются следующие тождества: ${\ displaystyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, 0)}$${\ displaystyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, 1)}$

${\ displaystyle f_ {i-1} (r_ {1}, \ dots, r_ {i-1}) = {\ begin {cases} f_ {i} (r_ {1}, \ dots, r_ {i-1) }, 0) \ cdot f_ {i} (r_ {1}, \ dots, r_ {i-1}, 1) & {\ mathsf {S}} = \ forall \\ f_ {i} (r_ {1} , \ dots, r_ {i-1}, 0) * f_ {i} (r_ {1}, \ dots, r_ {i-1}, 1) & {\ mathsf {S}} = \ exists. \ end {случаи}}}$

${\ displaystyle f_ {i-1} (r_ {1} \ dots r) = (1-r) f_ {i} (r_ {1}, \ dots, r_ {i-1}, 0) + rf_ {i } (r_ {1}, \ dots, r_ {i-1}, 1) {\ text {if}} {\ mathsf {S}} = \ mathrm {R}.}$

Если что-то не удается, откажитесь.

V → P : V выбирает случайный r из F и отправляет его в P. (Если тогда это r заменяет предыдущее r ). ${\ Displaystyle {\ mathsf {S}} = \ mathrm {R}}$

Перейти к фазе i  + 1, где P должен убедить V, что он прав. ${\ displaystyle f_ {i} (r_ {1}, \ dots, r)}$

• Фаза k + 1 : V оценивает . Затем он проверяет , равны ли они, тогда V принимает, иначе V отклоняет.${\ displaystyle p (r_ {1}, \ dots, r_ {m})}$${\ displaystyle p (r_ {1}, \ dots, r_ {m}) = f_ {k} (r_ {1}, \ dots, r_ {m})}$

Это конец описания протокола.

Если ψ истинно, то V примет, когда P следует протоколу. Точно так же, если злонамеренный доказывающий, который лжет, и если ψ ложно, тогда нужно будет лечь на фазе 0 и отправить какое-то значение для f ₀ . Если в фазе I , V имеет неправильное значение , то и будет , вероятно , также будет неправильно, и так далее. Вероятность повезти на некотором случайном г самое большее степень полинома , деленному на размер поля: . Протокол проходит через O ( n ² ) фаз, поэтому вероятность того, что на каком-то этапе вам повезет, составляет ≤ 1 / n . Если никогда не повезет, то V откажется на фазе k +1. ${\ displaystyle {\ tilde {P}}}$${\ displaystyle {\ tilde {P}}}$${\ displaystyle f_ {я-1} (r_ {1}, \ точки)}$${\ displaystyle f_ {i} (r_ {1}, \ dots, 0)}$${\ displaystyle f_ {i} (r_ {1}, \ dots, 1)}$${\ displaystyle {\ tilde {P}}}$${\ Displaystyle п / п ^ {4}}$${\ displaystyle {\ tilde {P}}}$${\ displaystyle {\ tilde {P}}}$

Поскольку теперь мы показали, что и IP ⊆ PSPACE, и PSPACE ⊆ IP , мы можем сделать вывод, что IP = PSPACE, как и нужно . Более того, мы показали, что любой IP- алгоритм может рассматриваться как публичная монета, поскольку сокращение от PSPACE к IP обладает этим свойством.

Варианты

Есть несколько вариантов IP, которые немного изменяют определение интерактивной системы доказательства. Мы резюмируем некоторые из наиболее известных здесь.

окунать

Подмножество IP - это детерминированный класс интерактивного доказательства , который подобен IP, но имеет детерминированный верификатор (то есть без случайности). Этот класс равен NP .

Идеальная полнота

Эквивалентное определение IP заменяет условие , что взаимодействие преуспевает с высокой вероятностью на строки в языке с требованием , чтобы он всегда преуспевает:

${\ displaystyle w \ in L \ Rightarrow \ Pr [V \ leftrightarrow P {\ text {принимает}} w] = 1}$

Этот, казалось бы, более сильный критерий «идеальной полноты» не меняет класс сложности IP , поскольку любому языку с интерактивной системой доказательства может быть предоставлена ​​интерактивная система доказательства с идеальной полнотой.

MIP

В 1988 году Goldwasser et al. создали еще более мощную интерактивную систему доказательства, основанную на IP, под названием MIP, в которой есть два независимых доказывающих. Два доказывающих не могут обмениваться данными после того, как проверяющий начал посылать им сообщения. Так же, как легче определить, лжет ли преступник, если его и его партнера допрашивают в разных комнатах, гораздо проще обнаружить злонамеренного доказывающего, пытающегося обмануть проверяющего, если есть другой доказывающий, с которым он может перепроверить. Фактически, это настолько полезно, что Бабай, Фортноу и Лунд смогли показать, что MIP = NEXPTIME , класс всех задач, решаемых недетерминированной машиной за экспоненциальное время , очень большой класс. Более того, все языки в NP имеют доказательства с нулевым разглашением в системе MIP без каких-либо дополнительных предположений; это известно только для IP, предполагающего существование односторонних функций.

IPP

IPP ( неограниченный IP ) - это вариант IP, в котором мы заменяем верификатор BPP на верификатор PP . Точнее, модифицируем условия полноты и правильности следующим образом:

• Полнота : если строка находится на языке, честный проверяющий убедится в этом факте с вероятностью не менее 1/2.
• Правильность : если строка не на языке, ни один проверяющий не сможет убедить честного проверяющего, что она на языке, за исключением случаев, когда вероятность меньше 1/2.

Хотя IPP также равен PSPACE , протоколы IPP ведут себя совершенно иначе, чем IP в отношении оракулов : IPP = PSPACE по отношению ко всем оракулам, а IP ≠ PSPACE по отношению почти ко всем оракулам.

QIP

QIP - это версия IP, заменяющаяверификатор BPP на верификатор BQP , где BQP - это класс задач, решаемых квантовыми компьютерами за полиномиальное время. Сообщения состоят из кубитов. В 2009 году Jain, Ji, Upadhyay и Watrous доказали, что QIP также соответствует PSPACE , подразумевая, что это изменение не дает протоколу дополнительных возможностей. Это включает предыдущий результат Китаева и Уотроуса о том, что QIP содержится в EXPTIME, потому что QIP = QIP [3], так что больше трех раундов никогда не требуется.

compIP

В то время как IPP и QIP дают больше возможностей верификатору, система compIP ( конкурентная система подтверждения IP ) ослабляет условие полноты таким образом, что ослабляет доказывающий:

• Полнота : если строка написана на языке L , честный проверяющий убедится в этом факте с вероятностью не менее 2/3. Кроме того, доказывающий будет делать это в вероятностном полиномиальное время получили доступ к оракулу для языка L .

По сути, это делает доказывающий машину BPP с доступом к оракулу для языка, но только в случае полноты, а не в случае разумности. Идея состоит в том, что если язык входит в состав compIP , то интерактивно доказать его в каком-то смысле так же просто, как принять решение. С помощью оракула проверяющий может легко решить проблему, но его ограниченные возможности значительно затрудняют убеждение проверяющего в чем-либо. Фактически, compIP даже не известно и не предполагается, что он содержит NP .

С другой стороны, такая система может решить некоторые проблемы, которые считались сложными. Как это ни парадоксально, хотя считается, что такая система не может решить все NP , она может легко решить все NP-полные проблемы благодаря самовосстановлению. Это происходит из-за того, что если язык L не является NP- жестким, программа доказательства существенно ограничена в возможностях (поскольку она больше не может решать все проблемы NP с помощью своего оракула).

Кроме того, проблема неизоморфизма графов (которая является классической проблемой в IP ) также находится в compIP , поскольку единственная трудная операция, которую должен выполнить проверяющий, - это проверка изоморфизма, для решения которой он может использовать оракул. Квадратичная неотъемлемость и изоморфизм графов также находятся в compIP . Обратите внимание, что квадратичная неостаточность (QNR), вероятно, является более простой проблемой, чем изоморфизм графов, поскольку QNR находится в UP, пересекающем co-UP .

Примечания

использованная литература

• Бабай Л. Теория торговых групп для случайности. В материалах 17-го симпозиума ACM по теории вычислений. ACM, Нью-Йорк, 1985, стр. 421–429.
• Шафи Гольдвассер , Сильвио Микали и Чарльз Ракофф . Сложность знаний интерактивных доказательств . Труды 17-го симпозиума ACM по теории вычислений , Провиденс, Род-Айленд. 1985, с. 291–304. Расширенная аннотация
• Шафи Гольдвассер и Майкл Сипсер. Частные монеты против публичных монет в интерактивных системах проверки . Материалы 18-го ежегодного симпозиума ACM по теории вычислений . ACM, Нью-Йорк, 1986, стр. 59–68.
• Рахул Джайн, Чжэнфэн Джи, Сарвагья Упадхьяй, Джон Уотрус. QIP = PSPACE. [1]
• Лунд, К. , Фортноу, Л. , Карлофф, Х., Нисан, Н. Алгебраические методы для интерактивных систем доказательства. В материалах 31-го симпозиума по основам информатики. IEEE, Нью-Йорк, 1990, стр. 2–90.
• Ади Шамир. IP = PSPACE . Журнал ACM , том 39, выпуск 4, стр. 869–877. Октябрь 1992 г.
• Александр Шен. IP = PSpace: упрощенное доказательство . J.ACM, v. 39 (4), pp. 878–880, 1992.
• Зоопарк сложности : IP , MIP , IPP , QIP , QIP (2) , compIP , frIP