ИП (сложность)

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

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

Общее представление протокола интерактивного доказательства.

Определение

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

$w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]\geq {\tfrac {2}{3}}$

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

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

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

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

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

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

IP ⊆ PSPACE

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

$\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j}]=\max \nolimits _{P}\Pr \left[V\leftrightarrow P{\text{ accepts }}w{\text{ starting at }}M_{j}\right]$

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

$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{ is odd}}\\{\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}&j<p{\text{ and }}j{\text{ is even}}\\\end{cases}}$

где:

${\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 четно, m _j+1 это сообщение от V к P. — По определению N _{M j} ,

$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}}.$

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

$\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\left[V(w,r,M_{j})=m_{j+1}\right]*\Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right].$

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

Если j нечетно, m _j+1 это сообщение от P к V. — По определению,

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

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

$\max \nolimits _{m_{j+1}}*\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}].$

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

$\max \nolimits _{m_{j+1}}\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}]\leq \Pr[V{\text{ accepts w starting at }}M_{j}]$

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

$\max \nolimits _{m_{j+1}}\Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right]\geq \Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j}\right]$

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

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

PSPACE ⊆ IP

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

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

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

$\#{\text{SAT}}=\left\{\langle \varphi ,k\rangle \ :\ \varphi {\text{ is a CNF-formula with exactly }}k{\text{ satisfying assignments}}\right\}.$

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

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

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

а ∧ б	аб
а ∨ б	а * б := 1 - (1 - а ) (1 - б )
¬ a	1 − а

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

${\begin{aligned}p_{\varphi }&=a\wedge (b\vee \neg c)\\&=a\wedge \left(b*(1-c)\right)\\&=a\wedge \left(1-(1-b)(1-(1-c))\right)\\&=a\left(1-(1-b)(1-(1-c))\right)\\&=a-(ac-abc)\end{aligned}}$

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

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

$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 ₀ — пустая функция без переменных.

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

• Фаза 0 : Доказывающая P выбирает простое число q > 2. ^н и вычисляет f ₀ , затем отправляет q и 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 отправляет коэффициенты $f_{i}(r_{1},\dots ,r_{i-1},z)$ как многочлен от z . V что степень fi _{проверяет ,} меньше n и что $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)$. (Если нет, Ви отклоняет). V отправляет случайное число r _i из F в P. Теперь
• Фаза n+1 : V оценивает $p(r_{1},\dots ,r_{n})$ для сравнения со значением $f_{n}(r_{1},\dots ,r_{n})$. Если они равны , V принимает, в противном случае — отклоняет.

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

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

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

$\Pr \left[{\tilde {f}}_{1}(r_{1})=f_{1}(r_{1})\right]<{\tfrac {1}{n^{2}}}.$

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

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

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

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

$\Pr \left[{\tilde {f}}(r_{1},\dots ,r_{i})=f_{i}(r_{1},\dots ,r_{i})\right]\leq {\tfrac {1}{n^{2}}}.$

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

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

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

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

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

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

$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{ is true}}\\0&{\text{otherwise}}\end{cases}}$

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

$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}=\exists \end{cases}}$

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

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

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

$\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 ]$

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

$\psi '={\mathsf {S}}_{1}y_{1}\dots {\mathsf {S}}_{k}y_{k}[\varphi ],\qquad {\text{ where }}{\mathsf {S}}_{i}\in \{\forall ,\exists ,\mathrm {R} \},\ y_{i}\in \{x_{1},\dots ,x_{m}\}$

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

${\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)$

${\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)$

${\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 . Также после любого ${\mathsf {Q}}_{i}x_{i}$ мы добавляем $\mathrm {R} _{x_{1}}\dots \mathrm {R} _{x_{i}}$ в ψ′, чтобы после арифметизации понизить степень до 1 ${\mathsf {Q}}_{i}$.

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

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

$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 отправляет $f_{i}(r_{1},\dots ,r_{i-1},z)$ как многочлен от z . r ₁ обозначает ранее установленные случайные значения для $r_{1},\dots ,r_{i-1}$

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

$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{cases}}$

$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. (Если ${\mathsf {S}}=\mathrm {R}$ тогда это r заменяет предыдущее r ).

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

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

На этом описание протокола заканчивается.

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

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

Варианты

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

дип

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

Подмножеством IP является детерминированный класс Interactive Proof , который похож на IP, но имеет детерминированный верификатор (т. е. без случайности).Этот класс равен NP .

Совершенная полнота

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

$w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]=1$

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

МИП

Основная статья: Интерактивная система доказательств § MIP

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

ИПП

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

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

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

КИП

Основная статья: Квантовый интерактивный протокол

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

компИП

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

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

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

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

Кроме того, проблема неизоморфизма графа (которая является классической проблемой в IP ) также присутствует в compIP , поскольку единственная сложная операция, которую должен выполнить доказывающий, — это проверка изоморфизма, для решения которой он может использовать оракул. Квадратичная нерезультатность и изоморфизм графов также есть в compIP . Обратите внимание: квадратичная неостаточность (QNR), вероятно, является более простой проблемой, чем изоморфизм графа, поскольку QNR находится в UP intersect 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 . Журнал АКМ , том 39, выпуск 4, с. 869–877. Октябрь 1992 года.
• Александр Шен. IP=PSpace: упрощенное доказательство . J.ACM, т. 39 (4), стр. 878–880, 1992 г.
• Зоопарк сложности : IP , MIP. Архивировано 3 июня 2013 г. в Wayback Machine . IPP. Архивировано г. в Wayback Machine . , QIP Архивировано в Wayback Machine . 14 марта 2014 3 июня 2013 г. 14 на Wayback Machine , compIP Архивировано 21 мая 2013 г. на Wayback Machine , frIP Архивировано 3 июня 2013 г. на Wayback Machine