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

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

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

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

Определение

Язык L принадлежит IP если есть V, п такой, что для всех Q, ш:

{ 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 ≤ п и история каждого сообщения 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

куда:

{ 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_р вероятность, взятая по случайной строке р длины п. Это выражение представляет собой среднее значение N_{M_{j + 1}}, взвешенная по вероятности того, что проверяющий отправил сообщение м_{j + 1}.

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

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

Базовый случай j = п довольно просто. С м_п либо принять, либо отклонить, если м_п принимает, N_{M_п} определяется как 1 и Pr [V принимает ш начинается с M_j] = 1, поскольку поток сообщений указывает на принятие, поэтому утверждение верно. Если м_п это отклонить, аргумент очень похож.

В качестве индуктивного предположения мы предполагаем, что для некоторого j+1 ≤ п и любая последовательность сообщений M_{j + 1}, N_{M_{j + 1}} = Pr [V принимает ш начинается с 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 принимает ш начинается с M_j].

Если j странно, м_{j + 1} это сообщение от п к 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 принимает ш начинается с M_j] поскольку:

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

потому что доказывающая сторона справа может отправить сообщение м_{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]}

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

Здесь мы построили машину с полиномиальным пространством, в которой используется лучший доказывающий п для конкретной строки ш на языке А. Мы используем этот лучший прувер вместо прувера со случайными входными битами, потому что мы можем опробовать каждый набор случайных входных битов в полиномиальном пространстве. Поскольку мы смоделировали интерактивную систему доказательства с помощью машины с полиномиальным пространством, мы показали, что 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 {, удовлетворяющими присваиваниям }}верно}.}

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

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

Правила арифметизации для преобразования булевой формулы φ (б₁, ..., *б_п*) к многочлену п_φ(*Икс*₁, ..., *Икс_п*)
а ∧ б	ab
а ∨ б	а ∗ б := 1 − (1 − а)(1 − б)
¬а	1 − а

Например, φ = а ∧ б ∨ ¬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 и а ∗ б каждый результат в полиноме со степенью, ограниченной суммой степеней полиномов для а и б и, следовательно, степень любой переменной не больше длины φ.

Теперь позвольте F - конечное поле с порядком q > 2^п; также потребуйте, чтобы q было не менее 1000. Для каждого 0 ≤ я ≤ п, определите функцию ж_я на F, имеющий параметры ${ displaystyle a_ {1}, dots, a_ {i-1} in F}$ , и единственная переменная а_я в F: Для 0 ≤ я ≤ п и для ${ 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}).}

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

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

Фаза 0: Испытатель п выбирает прайм q > 2^п и вычисляет ж, затем он отправляет q и ж₀ к верификатору V. V проверяет это q простое число больше max (1000, 2^п) и что ж₀() = k.
Фаза 1: п отправляет коэффициенты ж₁(z) как многочлен от z. V проверяет, что степень ж₁ меньше чем п и это ж₀ = ж₁(0) + ж₁(1). (Если не V отклоняет). V теперь отправляет случайное число р₁ из F к п.
Фаза i: п отправляет коэффициенты ${ displaystyle f_ {i} (r_ {1}, dots, r_ {i-1}, z)}$ как полином от z. V проверяет, что степень ж_я меньше чем п и это ${ 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)}$ . (Если не V отклоняет). V теперь отправляет случайное число р_я из F к п.
Фаза n + 1: V оценивает ${ displaystyle p (r_ {1}, dots, r_ {n})}$ сравнивать со значением ${ displaystyle f_ {n} (r_ {1}, dots, r_ {n})}$ . Если они равны V принимает, иначе V отклоняет.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, прежде чем арифметизировать ${ 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_ {м} }}

Теперь для каждого я ≤ k мы определяем функцию ж_я. Мы также определяем ${ displaystyle f_ {k} (x_ {1}, dots, x_ {m})}$ быть полиномом п(Икс₁, ..., Икс_м), который получается арифметизацией φ. Теперь, чтобы сохранить степень полинома низкой, определим ж_я с точки зрения ж_{я + 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)}

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

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

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

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

V использует коэффициенты для оценки ${ 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 → п: V выбирает случайный р в F и отправляет его P. (Если ${ Displaystyle { mathsf {S}} = mathrm {R}}$ тогда это р заменяет предыдущий р).

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

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

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

Если ψ истинно, то V приму когда п следует протоколу. Аналогично, если ${ displaystyle { tilde {P}}}$ злонамеренный доказывающий, который лжет, и если ψ ложно, то ${ displaystyle { tilde {P}}}$ нужно будет находиться в фазе 0 и отправить какое-то значение для ж₀. Если на этапе я, V имеет неверное значение для ${ 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}}}$ повезет на какой-то фазе ≤ 1 /п. Если ${ displaystyle { tilde {P}}}$ никогда не везет, тогда V отклонят на этапе k+1.

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

Варианты

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

окунать

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

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

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

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

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

MIP

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

IPP

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

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

Несмотря на то что IPP также равно PSPACE, IPP протоколы ведут себя совершенно иначе, чем IP относительно оракулы: IPP=PSPACE по отношению ко всем оракулам, а IP ≠ PSPACE относительно почти всех оракулов.^[5]

QIP

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

compIP

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

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

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

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

Кроме того, проблема неизоморфизма графов (что является классической проблемой в IP) также в compIP, поскольку единственная трудная операция, которую должен выполнить проверяющий, - это проверка изоморфизма, для решения которой он может использовать оракул. Квадратичная неотъемлемость и изоморфизм графов также находятся в compIP.^[9] Обратите внимание: квадратичная неостаточность (QNR), вероятно, является более простой проблемой, чем изоморфизм графов, поскольку QNR находится в ВВЕРХ пересекаться совместная работа.^[10]

Примечания

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

Важный классы сложности (более )
Считается выполнимым	DLOGTIME AC⁰ АКК⁰ TC⁰ L SL RL NL NC SC CC п P-полный ЗПП RP BPP BQP APX
Подозревается в невозможности	ВВЕРХ НП НП-полный NP-жесткий со-НП совместно NP-полный ЯВЛЯЮСЬ QMA PH ⊕P PP #П # P-complete IP PSPACE PSPACE-полный
Считается невозможным	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME НАЧАЛЬНЫЙ PR р RE ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерархия Гжегорчика Арифметическая иерархия Логическая иерархия
Семьи классов	DTIME NTIME DSPACE NSPACE Вероятностно проверяемое доказательство Интерактивная система доказательств