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

редактировать

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

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

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

Содержание

1 Определение
2 Доказательство IP = PSPACE
- 2.1 IP ⊆ PSPACE
- 2.2 PSPACE ⊆ IP
  - 2.2.1 #SAT является участником IP
  - 2.2.2 TQBF является членом IP
3 Варианта
- 3.1 dIP
- 3.2 Совершенная полнота
- 3.3 MIP
- 3.4 IPP
- 3.5 QIP
- 3.6 compIP
4 Примечания
5 Ссылки

Определение

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

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

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

w ∉ L ⇒ Pr [V ↔ Q принимает w] ≤ 1 3 {\ displaystyle w \ not \ in L \ Rightarrow \ Pr [V \ leftrightarrow Q {\ text {принимает}} w] \ leq { \ tfrac {1} {3}}}

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

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

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

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

Доказательство IP = PSPACE

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

IP ⊆ PSPACE

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

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

\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 Mj:

NM j = {0 j = p и mp = reject 1 j = p и mp = accept max mj + 1 NM j + 1 j < p and j is odd wt-avg m j + 1 N M j + 1 j < p and j is even {\displaystyle N_{M_{j}}={\begin{cases}0j=p{\text{ and }}m_{p}={\text{reject}}\\1j=p{\text{ and }}m_{p}={\text{accept}}\\\max _{m_{j+1}}N_{M_{j+1}}j

N_{{M_{j}}}={\begin{cases}0j=p{\text{ and }}m_{p}={\text{reject}}\\1j=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}}

где:

wt-avg mj + 1 NM j + 1: = ∑ mj + 1 Pr r [V (w, r, M j) = mj + 1] NM j + 1 {\ 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}}}

{\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.

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

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

Базовый случай j = p довольно прост. Поскольку m p либо принять, либо отклонить, если m p принято, N Mpопределяется как 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 Mj,

NM j = ∑ mj + 1 Pr r [V (w, r, M j) = mj + 1] NM j + 1. {\ 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}}.}

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

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

∑ mj + 1 Pr r [V (w, r, M j) = mj + 1] ∗ Pr [V принимает w, начиная с 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].}

\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, начиная с M j ].

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

N M j = max m j + 1 N M j + 1. {\ displaystyle N_ {M_ {j}} = \ max \ nolimits _ {m_ {j + 1}} N_ {M_ {j + 1}}.}

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

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

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

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

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

max mj + 1 Pr [V принимает w, начиная с 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}]}

\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 mj + 1 Pr [V принимает w, начиная с M j + 1] ≥ Pr [V принимает w, начиная с M j] {\ displaystyle \ max \ nolimits _ {m_ {j + 1}} \ Pr \ left [V {\ text {принимает}} w {\ text {начиная с}} M_ {j + 1} \ right] \ geq \ Pr \ left [V {\ text {принимает}} w {\ text {начало at}} M_ {j} \ right]}

\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, мы сначала докажем более слабую теорему, которая была доказана Lund et al. др.: #SAT ∈ IP . Затем, используя концепции этого доказательства, мы расширим его, чтобы показать, что TQBF ∈ IP . Поскольку TQBF ∈ PSPACE -complete и TQBF ∈ IP, тогда PSPACE ⊆ IP.

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

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

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

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

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

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

Правила арифметизации для преобразования булевой формулы φ (b 1,..., b n) в полином p φ(x1,..., x n)
a ∧ b	ab
a ∨ b	a ∗ b: = 1 - (1 - a) (1 - b)
¬a	1 - a

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

p φ = a ∧ b ∨ ¬ c = a ∧ (b ∗ (1 - c)) = a ∧ (1 - ( 1 - b) (1 - (1 - c))) = a (1 - (1 - b) (1 - (1 - c))) = a - (ac - abc) {\ displaystyle {\ begin {выровнено } 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 {align}}}

{\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,…, ai - 1 ∈ F {\ displaystyle a_ {1}, \ dots, a_ {i-1} \ in F}$ $a_{1},\dots,a_{{i-1}}\in F$ и одна переменная a i в F: для 0 ≤ i ≤ n и для $a 1,…, ai ∈ F {\ displaystyle a_ {1}, \ dots, a_ {i} \ in F}$ $a_{1},\dots,a_{i}\in F$ пусть

fi (a 1,…, ai) = ∑ ai + 1,…, an ∈ {0, 1} p (a 1,…, an). {\ 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_{i}(a_{1},\dots,a_{i})=\sum \nolimits _{{a_{{i+1}},\dots,a_{n}\in \{0,1\}}}p(a_{1},\dots,a_{n}).

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

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

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

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

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

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

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

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

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

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

f ~ i - 1 (r 1,…, ri - 1) ≠ fi - 1 (r 1,…, ri - 1), {\ displaystyle {\ tilde {f}} _ {i-1} (r_ {1}, \ dots, r_ {i-1}) \ neq f_ {i-1 } (r_ {1}, \ dots, r_ {i-1}),}

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

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

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

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

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

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

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

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

ψ = Q 1 x 1… Q mxm [φ] {\ displaystyle \ psi = {\ mathsf {Q}} _ {1} x_ {1} \ dots {\ mathsf {Q}} _ {m} x_ {m} [\ varphi]}

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

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

fi (a 1,…, ai) = {fi (a 1,…, am) = 1 Q i + 1 xi + 1… Q mxm [φ (a 1,…, ai)] истинно 0 иначе {\ 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 {is true}} \\ 0 {\ text {else}} \ end {cases}}}

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 1,..., a i) - это φ с 1 на i, замененными на x 1 на x i. Таким образом, f 0 - это значение истинности для ψ. Для арифметизации ψ мы должны использовать следующие правила:

fi (a 1,…, ai) = {fi + 1 (a 1,…, ai, 0) ⋅ fi + 1 (a 1,…, ai, 1) Q я + 1 знак равно ∀ fi + 1 (a 1,…, ai, 0) ∗ fi + 1 (a 1,…, ai, 1) Q i + 1 = ∃ {\ 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} = \ exists \ end { case}}}

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},\do ts,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, который будет уменьшать степени полинома без изменения их поведения на булевых входах.

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

ψ ′ = Q 1 R x 1 Q 2 R x 1 R x 2 … Q м р Икс 1… R xm [φ] {\ 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]}

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

или иначе:

ψ ′ = S 1 y 1… S kyk [φ], где S i ∈ {∀, ∃, R}, yi ∈ {x 1,…, xm} {\ displaystyle \ 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}, \ точки, x_ {m} \}}

\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. Мы также определяем $fk (x 1,…, xm) {\ displaystyle f_ {k} (x_ {1}, \ dots, x_ {m})}$ $f_{k}(x_{1},\dots,x_{m})$ как многочлен p (x 1,..., x m), который получается арифметизацией φ. Теперь, чтобы сохранить низкую степень полинома, мы определяем f i в терминах f i + 1 :

Если S i + 1 = ∀, fi (a 1,…, ai) = fi + 1 (a 1,…, ai, 0) ⋅ fi + 1 (a 1,…, ai, 1) {\ 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)}

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

Если S i + 1 = ∃, fi (a 1,…, ai) = fi + 1 ( a 1,…, ai, 0) ∗ fi + 1 (a 1,…, ai, 1) {\ displaystyle {\ text {If}} {\ mathsf {S}} _ {i + 1} = \ существует, \ 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}=\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)

Если S i + 1 = R, fi (a 1,…, ai, a) = (1 - a) fi + 1 (a 1,…, ai, 0) + afi + 1 (a 1,…, ai, 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)}

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

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

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

f 0 (∅) = {f 1 (0) ⋅ f 1 (1), если S = ​​∀ f 1 (0) ∗ f 1 (1), если S = ​​∃. (1 - r) f 1 (0) + r f 1 (1), если S = ​​R. {\ 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}}}

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

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

fi - 1 (r 1,…, ri - 1) = {fi (r 1,…, ri - 1, 0) ⋅ fi (r 1,…, ri - 1, 1) S = ∀ fi (r 1,…, ri - 1, 0) ∗ fi (r 1,…, ri - 1, 1) S = ∃. {\ 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 {case}}}

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

fi - 1 (r 1… r) = (1 - r) fi (r 1,…, ri - 1, 0) + rfi (r 1,…, ri - 1, 1) если S = ​​R. {\ 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}.}

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

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

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

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

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

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

Варианты

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

dIP

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

Perfect Completeness

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

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

w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}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 году Джайн, Джи, Упадхьяй и Уотроус доказали, что QIP также равно PSPACE, подразумевая, что это изменение не дает протоколу дополнительных возможностей. Это включает предыдущий результат Китаева и Уотроуса, согласно которому QIP содержится в EXPTIME, потому что QIP = QIP [ 3], так что никогда не потребуется более трех раундов.

compIP

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

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

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

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

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

Примечания

^Lund, C.; Fortnow, L.; Karloff, H.; Нисан, Н. (1990). «Алгебраические методы для интерактивных систем доказательства». Труды [1990] 31-й ежегодный симпозиум по основам информатики. IEEE Comput. Soc. Нажмите: 2–10. doi : 10.1109 / fscs.1990.89518. ISBN 0-8186-2082-X.
^Шамир, Ади. "Ip = pspace." Журнал ACM 39.4 (1992): 869-877.
^Чанг Ричард; и другие. (1994). «Гипотеза случайного оракула неверна». Журнал компьютерных и системных наук. 49 (1): 24–39. doi : 10.1016 / s0022-0000 (05) 80084-4.
^Фурер Мартин, Голдрайх Одед, Мансур Ишай, Сипсер Майкл, Захос Статис (1989). «О полноте и надежности в интерактивных системах проверки». Достижения в области компьютерных исследований: ежегодное исследование. 5 : 429–442. CiteSeerX 10.1.1.39.9412. CS1 maint: несколько имен: список авторов (ссылка )
^R. Chang, B. Chor, Oded Goldreich, J. Хартманис, Дж. Хастад, Д. Ранджан и П. Рохатги. Гипотеза случайного оракула ложна. Journal of Computer and System Sciences, 49 (1): 24-39.1994.
^Дж. Уотроус. PSPACE имеет квантовые интерактивные системы доказательства с постоянным циклом. Proceedings of IEEE FOCS'99, pp. 112-119. 1999.
^Рахул Джайн; Чжэнфэн Джи; Сарвагья Упадхьяй; Джон Уотроус (2009). "QIP = PSPACE". arXiv : 0907.4737 [Quant-ph ].
^А. Китаев и Дж. Уотроус. Распараллеливание, усиление и экспоненциальное моделирование во времени квантовых интерактивных систем доказательства. Труды 32-го симпозиума ACM по теории вычислений, стр. 608-617. 2000.
^Шафи Гольдвассер и Михир Белларе. Сложность принятия решения по сравнению с поиском. SIAM Journal on Computing, Volume 23, No. 1. Февраль 1994 г.
^Cai JY, Threlfall RA (2004) ». Примечание о квадратичной остаточности и UP ". Письма об обработке информации. 92 (3): 127–131. CiteSeerX 10.1.1.409.1830. doi :10.1016/j.ipl.2004.06.015.

References

Babai, L. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation. ACM, New York, 1985, pp. 421–429.
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge complexity of interactive proof-systems. Proceedings of 17th ACM Symposium on the Theory of Computation, Providence, Rhode Island. 1985, pp. 291–304. Extended abstract
Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Proceedings of the 18th Annual ACM Symposium on Theory of Computation. ACM, New York, 1986, pp. 59–68.
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [1]
Lund, C., Fortnow, L., Karloff, H., Nisan, N. Algebraic methods for interactive proof systems. In Proceedings of 31st Symposium on the Foundations of Computer Science. IEEE, New York, 1990, pp. 2–90.
Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p. 869–877. October 1992.
Alexander Shen. IP=PSpace: Simplified Proof. J.ACM, v. 39(4), pp. 878–880, 1992.
Complexity Zoo : IP, MIP, IPP, QIP, QIP(2), compIP, frIP