IP（複雑さ）

計算複雑性理論において、クラスIP（対話型証明）は、対話型証明システムによって解ける問題のクラスである。これはクラスPSPACEに等しい。この結果は一連の論文によって確立された。最初の論文では、Lund、Karloff、Fortnow、Nisan が、co-NPには複数の証明者対話型証明が存在することを示した。^[1]そして2番目の論文では、Shamirが彼らの手法を用いて IP=PSPACE であることを証明した。^{[2]この結果は、証明が}相対化されない有名な例である。^[3]

対話型証明システムの概念は、1985 年にShafi Goldwasser、Silvio Micali、Charles Rackoffによって初めて導入されました。対話型証明システムは、与えられた文字列nが何らかの言語のメンバーであるという証明を提示する証明器Pと、提示された証明が正しいことを確認する検証器Vの 2 つのマシンで構成されます。証明器は計算量と記憶容量が無限であると想定され、検証器は、長さがnのサイズの多項式であるランダムビット文字列にアクセスできる確率多項式時間マシンです。これら 2 つのマシンは多項式数p ( n ) のメッセージを交換し、対話が完了すると、検証器はnが言語内にあるかどうかを、エラーの可能性が 1/3 しかない状態で判断する必要があります (したがって、BPPの言語はすべてIP内にあり、その場合は検証器は証明器を無視して独自に判断することができます)。

意味

言語LがIPに属するのは、任意のQ、wに対してV、Pが存在する場合である。

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

László Babaiによって導入されたArthur–Merlin プロトコルは、相互作用のラウンド数が多項式ではなく定数によって制限されることを除いて、本質的には同様です。

Goldwasserらは、検証者が使用する乱数がチャレンジと共に証明者に提供される公開コインプロトコルが、非公開コインプロトコルと同等の強力さを持つことを示しました。非公開コインプロトコルの効果を再現するには、最大で2ラウンドの追加的なやり取りが必要です。反対に、検証者は非公開コインの投げた結果を常に証明者に送信できるため、非公開コインプロトコルの組み込みは容易であり、2種類のプロトコルが同等であることが証明されます。

次のセクションでは、計算の複雑さに関する重要な定理であるIP = PSPACEを証明します。この定理は、従来のPSPACE証明が指数的に長くなる可能性がある場合でも、対話型証明システムを使用して、文字列が言語のメンバーであるかどうかを多項式時間で決定できることを示しています。

IPの証明 = PSPACE

証明は2つの部分に分けられ、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は長さpのランダム文字列rにおける確率です。この式は、検証者がメッセージm _j+1を送信した確率で重み付けされたN _M_{_j+1}の平均です。

M _{0 を}空のメッセージシーケンスとすると、 N _{M _{0 は}}多項式空間で計算でき、N _{M ₀} = Pr[ V accepts w ] であることを示します。まず、N _{M ₀}を計算するために、アルゴリズムはすべてのjとM _jに対して値N _{M _j}を再帰的に計算できます。再帰の深さはpなので、必要なのは多項式空間のみです。2つ目の要件は、w がA に含まれるかどうかを判断するために必要な値であるN _M_₀ = Pr[ V accepts w ] が必要であることです。これは、次のように帰納法を用いて証明します。

0 ≤ j ≤ pかつ任意のM _jに対して、N _{M _j} = Pr[ V はM _jから始まるw を受け入れる] ことを示さなければなりません。これはjに関する帰納法を用いて行います。基本ケースはj = pの場合の証明です。次に、帰納法を用いてpから0 までを導きます。

j = pの基本ケースは非常に単純です。m _pは accept か refuse のいずれかであるため、m p が accept の場合、N _M pは_{1_と}定義され、Pr[ VはM _jからw を受け入れる] = 1 となります。これは、メッセージストリームが accept を示しているためです。したがって、主張は真です。m p が refuse の場合も、_議論はほぼ同様です。

帰納的仮説については、あるj +1 ≤ pと任意のメッセージシーケンスM _j+1に対して、 N _{M _j+1} = Pr[ V はM _j+1からw を受け入れる] と仮定し、次に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はM _jからwを受け入れる]に等しいことがわかります。

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はM _jからwを受け入れる]と等しい。

\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が完全であるという証明が成立する。

ここでは、言語Aの特定の文字列wに対して最適な証明器Pを用いる多項式空間マシンを構築した。この最適な証明器をランダム入力ビットを用いる証明器の代わりに用いるのは、多項式空間においてあらゆるランダム入力ビットの集合を試すことができるためである。多項式空間マシンを用いて対話型証明システムをシミュレートした結果、期待通りIP ⊆ PSPACEとなることが示された。

PSPACE ⊆ IP

PSPACE ⊆ IPを証明するための手法を説明するために、まずLundらによって証明されたより弱い定理、#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 ₁ , ..., *b _n* ) を多項式p _φ ( x ₁ , ..., *x _n* ) に変換するための算術規則
a ∧ b	腹筋
a ∨ b	a ∗ b := 1 − (1 − a )(1 − b )
¬ a	1 − a

たとえば、次のように多項式に変換されます。 $\phi =a\land (b\lor \neg 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の各値に対して、パラメータと1つの変数を持つ関数f _{i を}F上に定義します。0 ≤ i ≤ nおよびに対して、 $a_{1},\dots ,a_{i-1}\in F$ $a_{i}\in F$ $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 0_は変数を持たない空関数です。

現在、#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は拒否します）。VはFからPに乱数r ₁を送信します。
フェーズ i : P はzの多項式としての係数を送信します。Vはf _iの次数がn未満であること、およびであることを確認します(そうでない場合はV は拒否します)。VはFからPに乱数r _iを送信します。 $f_{i}(r_{1},\dots ,r_{i-1},z)$ $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)$
フェーズ n+1 : Vは値と比較します。等しい場合はVは受け入れ、等しくない場合はVは拒否します。 $p(r_{1},\dots ,r_{n})$ $f_{n}(r_{1},\dots ,r_{n})$

これはパブリックコインアルゴリズムであることに注意してください。

φがk個の満足な割り当てを持つ場合、 Vは明らかに受け入れる。φがk個の満足な割り当てを持たない場合、φがk個の満足な割り当てを持つとVを説得しようとする証明者が存在すると仮定する。これは低い確率でしか実行できないことを示す。 ${\tilde {P}}$

フェーズ0でVが拒否するのを防ぐには、 Pに誤った値を送信する必要があります。次に、フェーズ1で、 Pに誤った多項式を送信する必要があります。Vがランダムなr _{1を選択して}Pに送信すると、 ${\tilde {P}}$ ${\tilde {f}}_{0}()$ ${\tilde {P}}$ ${\tilde {f}}_{1}$ ${\tilde {f}}_{1}(0)+{\tilde {f}}_{1}(1)={\tilde {f}}_{0}()$

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

これは、最大次数dの単変数多項式は、常に0となる場合を除いて、d個以上の根を持つことができないためです。したがって、最大次数dの単変数多項式は、 d個の位でのみ等しくなります。| F | > 2 ⁿであるため、 r ₁がこれらの値のいずれかになる確率は、 n > 10の場合は最大で ( n /1000) ≤ ( n / n 3 ) です。n ≤ 10の場合は最大で ( n /1000) ≤ ( n / n ³ )です。 $n/2^{n}<n/n^{3}$

この考え方を他の位相に一般化すると、1 ≤ i ≤ nの各位相について、

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

次に、 Fからランダムに選ばれたr _iに対して、

\Pr \left[{\tilde {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です。 ${\tilde {P}}$

TQBFはIPのメンバーです

PSPACEがIPの部分集合であることを示すためには、 PSPACE完全問題を選び、それがIPに属することを示す必要があります。これを示せば、PSPACE ⊆ IPであることは明らかです。ここで示した証明手法は、Adi Shamirによるものです。

TQBFはPSPACE完全であることが分かっています。そこで、ψを量化ブール式とします。

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

ここで、 φはCNF式です。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 ) は、 x ₁～x _iをa ₁～a _iに置き換えたφ です。したがって、f _{0は ψ の}真理値です。 ψ を算術化するためには、以下の規則に従う必要があります。

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を定義します。また、を φ を算術的に表すことで得られる多項式p ( x ₁ , ..., x _m ) と定義します。ここで、多項式の次数を低く抑えるため、f _{i を}f _i+1を用いて定義します。 $f_{k}(x_{1},\dots ,x_{m})$

{\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に関して線形な結果を生成します。また、 any の後にψ′ を追加することで、を算術化した後に次数を 1 に減らしています。 ${\mathsf {Q}}_{i}x_{i}$ $\mathrm {R} _{x_{1}}\dots \mathrm {R} _{x_{i}}$ ${\mathsf {Q}}_{i}$

それではプロトコルについて説明しましょう。nをψ の長さとすると、プロトコル内のすべての算術演算は、nを ψ の長さとしたとき、少なくともn ⁴の大きさの体上で行われます。

フェーズ0：P → V：Pはf _0をVに送信します。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はzの多項式として送信されます。r _1は、以前に設定されたランダム値を表します。 $f_{i}(r_{1},\dots ,r_{i-1},z)$ $r_{1},\dots ,r_{i-1}$

Vは係数を用いて、およびを評価します。そして、多項式の次数が最大でnであり、以下の恒等式が成り立つことを確認します。 $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})={\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 はFからランダムにrを選択し、それを P に送信します。(この場合、このrは前のrを置き換えます)。 ${\mathsf {S}}=\mathrm {R}$

フェーズi + 1に進み、 P はVにそれが正しいと説得する必要があります。 $f_{i}(r_{1},\dots ,r)$

フェーズk + 1 : V はを評価します。次に、が等しいかどうかを確認します。等しい場合はV は受け入れ、等しくない場合はVは拒否します。 $p(r_{1},\dots ,r_{m})$ $p(r_{1},\dots ,r_{m})=f_{k}(r_{1},\dots ,r_{m})$

これでプロトコルの説明は終わりです。

ψ が真であれば、P がプロトコルに従う場合、 V は受け入れます。同様に、が嘘をつく悪意のある証明者であり、 ψ が偽であれば、はフェーズ 0 で嘘をつき、 f ₀の値を送信する必要があります。フェーズiで、V はに誤った値を持ち、おそらくこれも誤りであり、以下同様です。がランダムrで幸運に恵まれる確率は、最大でも多項式の次数を体のサイズで割った値です。プロトコルはO ( n ² ) フェーズで実行されるため、あるフェーズでが幸運に恵まれる確率は≤ 1/ nです。が決して幸運に恵まれない場合、V はフェーズk +1で拒否します。 ${\tilde {P}}$ ${\tilde {P}}$ $f_{i-1}(r_{1},\dots )$ $f_{i}(r_{1},\dots ,0)$ $f_{i}(r_{1},\dots ,1)$ ${\tilde {P}}$ $n/n^{4}$ ${\tilde {P}}$ ${\tilde {P}}$

IP ⊆ PSPACEとPSPACE ⊆ IP の両方が成り立つことを示したので、期待通りIP = PSPACEと結論付けることができます。さらに、 PSPACEからIPへの還元がこの性質を持つため、任意のIPアルゴリズムは公開コインとして扱えることも示しました。

変種

IPには、対話型証明システムの定義をわずかに変更したいくつかの変種があります。ここでは、よく知られているもののいくつかをまとめます。

浸漬

IPのサブセットとして、決定論的インタラクティブ証明クラスがあります。これはIPに似ていますが、決定論的な検証器（つまりランダム性がない）を備えています。このクラスはNPと同等です。

完璧な完全性

IPの同等の定義では、言語内の文字列で相互作用が高確率で成功するという条件を、相互作用が常に成功するという要件に置き換えます。

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

この一見強い「完全性」という基準は、対話型証明システムを持つ言語には完全性を持つ対話型証明システムが与えられる可能性があるため、複雑性クラスIP を変更するものではありません。^[4]

MIP

1988 年、ゴールドワッサーらは、 IPをベースにしたさらに強力な対話型証明システムであるMIPを作成しました。MIP では、 2 人の独立した証明者が存在します。検証者が証明者にメッセージを送信し始めると、2 人の証明者は通信できなくなります。犯罪者とパートナーを別々の部屋で尋問すると嘘をついているかどうかが簡単にわかるのと同様に、悪意のある証明者が検証者を騙そうとしている場合、二重チェックできる別の証明者がいれば、その証明者を見抜くのはかなり簡単になります。実際、これは非常に役立つため、ババイ、フォートナウ、ルンドは、MIP = NEXPTIME 、つまり非決定性マシンで指数時間で解けるすべての問題のクラス、つまり非常に大きなクラスを示すことができました。さらに、NPのすべての言語は、追加の仮定なしに、 MIPシステムでゼロ知識証明を持ちます。これは、一方向性関数の存在を仮定するIPでのみ知られています。

IPP

IPP（非有界IP ）はIPの変種であり、BPP検証器をPP検証器に置き換えたものです。より正確には、完全性条件と健全性条件を以下のように変更します。

完全性: 文字列が言語内に存在する場合、正直な検証者は、少なくとも 1/2 の確率でこの事実を正直な証明者から確信されるでしょう。
健全性: 文字列が言語にない場合は、1/2 未満の確率を除いて、証明者は正直な検証者に文字列が言語にあることを納得させることができません。

IPPもPSPACEに等しいが、IPPプロトコルはオラクルに関してIPとは全く異なる動作をする。すべてのオラクルに関してIPP = PSPACEであるのに対し、ほとんどすべてのオラクルに関してIP ≠ PSPACEである。 ^[5]

QIP

QIPは、 BPP検証器をBQP検証器に置き換えたIPのバージョンである。ここで、 BQPは量子コンピュータが多項式時間で解ける問題のクラスである。メッセージは量子ビットで構成される。^[6] 2009年、Jain、Ji、Upadhyay、およびWatrousは、 QIPがPSPACEに等しいこと^{を証明した。 [7]}これは、この変更によってプロトコルに追加のパワーがもたらされないことを意味している。これは、KitaevとWatrousによる以前の結果、すなわちQIP = QIP [3]であるためQIPはEXPTIMEに含まれるおり、3ラウンド以上は必要ない。^[8]

コンプIP

IPPとQIP は検証者にさらなる力を与えますが、 compIPシステム (競合的 IP 証明システム) は、証明者を弱める方法で完全性条件を弱めます。

完全性：文字列が言語Lで記述されている場合、誠実な検証者は、誠実な証明者によって少なくとも 2/3 の確率でこの事実を確信します。さらに、証明者は言語Lのオラクルにアクセスできる場合、確率多項式時間でこれを証明します。

本質的に、これは証明者を言語のオラクルにアクセスできるBPPマシンにしますが、これは完全性の場合にのみアクセスでき、健全性の場合にはアクセスできません。この概念は、言語がcompIPに含まれる場合、それを対話的に証明することは、ある意味ではそれを判定するのと同じくらい簡単であるということです。オラクルがあれば、証明者は問題を簡単に解くことができますが、その能力が限られているため、検証者に何かを納得させることははるかに困難です。実際、compIPにはNPが含まれていることは知られておらず、また考えられていません。

一方で、このようなシステムは、困難と考えられているいくつかの問題を解くことができます。やや逆説的ですが、このようなシステムはNPのすべてを解けるとは考えられていませんが、自己還元性により、すべてのNP完全問題を容易に解くことができます。これは、言語LがNP困難でない場合、証明器の能力が大幅に制限されるという事実に起因しています（証明器はもはやオラクルですべてのNP問題を解くことができなくなるため）。

さらに、グラフ非同型性問題（ IPにおける古典的な問題）もcompIPに含まれる。これは、証明器が行う必要がある唯一の難しい演算は同型性のテストであり、これはオラクルを用いて解決できるためである。二次非残差性とグラフ同型性もcompIPに含まれる。^{[9]なお、二次非残差性（QNR）は}UP intersect co-UPに含まれるため、グラフ同型性よりも簡単な問題である可能性が高い。^[10]

注記

^ Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N. (1990). 「対話型証明システムのための代数的手法」. Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science . IEEE Comput. Soc. Press. pp. 2– 10. doi :10.1109/fscs.1990.89518. ISBN 0-8186-2082-X. S2CID 32614901。
^ シャミール、アディ。「Ip= pspace」ACMジャーナル39.4（1992）：869-877。
^ Chang Richard; et al. (1994). 「ランダムオラクル仮説は誤りである」. Journal of Computer and System Sciences . 49 (1): 24– 39. doi : 10.1016/s0022-0000(05)80084-4 .
^ Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis (1989). 「対話型証明システムにおける完全性と健全性について」. Advances in Computing Research: A Research Annual . 5 : 429–442 . CiteSeerX 10.1.1.39.9412 . {{cite journal}}: CS1 maint: multiple names: authors list (link)
^ R. Chang、B. Chor、Oded Goldreich、J. Hartmanis、J. Håstad、D. Ranjan、および P. Rohatgi。ランダムオラクル仮説は誤りです。ジャーナルオブコンピュータおよびシステムサイエンス、49(1):24-39。 1994年。
^ J. Watrous. PSPACEは定数ラウンドの量子インタラクティブ証明システムを持つ. IEEE FOCS'99論文集, pp. 112-119. 1999.
^ ラーフル・ジェイン;鄭峰季;サルヴァギャ・ウパディヤイ。ジョン・ワトラス(2009)。「QIP = PSPACE」。arXiv : 0907.4737 [quant-ph]。
^ A. KitaevとJ. Watrous. 量子対話型証明システムの並列化、増幅、指数時間シミュレーション.第32回ACM計算理論シンポジウム論文集、pp. 608-617. 2000.
^ シャフィ・ゴールドワッサーとミヒル・ベラーレ。意思決定と検索の複雑さ。SIAM Journal on Computing、第 23 巻、第 1 号、1994 年 2 月。
^ Cai JY, Threlfall RA (2004). 「二次残差と UPに関する注記」.情報処理レター. 92 (3): 127– 131. CiteSeerX 10.1.1.409.1830 . doi :10.1016/j.ipl.2004.06.015.

参考文献

ババイ, L. ランダムネスのためのトレーディング群論. 第17回ACM計算理論シンポジウム議事録. ACM, ニューヨーク, 1985年, pp. 421–429.
Shafi Goldwasser、Silvio Micali、Charles Rackoff . 対話型証明システムの知識複雑性.第17回ACM計算理論シンポジウム議事録、ロードアイランド州プロビデンス、1985年、pp. 291–304. 拡張概要Wayback Machineに2006年6月23日アーカイブ
Shafi GoldwasserとMichael Sipser. 対話型証明システムにおけるプライベートコインとパブリックコイン（2005年1月27日アーカイブ、Wayback Machine） . Proceedings of the 18th Annual ACM Symposium on Theory of Computation . ACM、ニューヨーク、1986年、pp. 59–68.
ラーフル・ジェイン、ジェンフェン・ジー、サルヴァギャ・ウパディヤイ、ジョン・ワトラス。 QIP = PSPACE。 [1]
Lund, C. , Fortnow, L. , Karloff, H. , Nisan, N.対話型証明システムのための代数的手法．第31回コンピュータサイエンス基礎シンポジウム論文集．IEEE, ニューヨーク, 1990, pp. 2–90.
Adi Shamir. IP = PSPACE. Journal of the ACM , 第39巻第4号, p. 869–877. 1992年10月.
アレクサンダー・シェン. IP=PSpace: 簡略化された証明. J.ACM, v. 39(4), pp. 878–880, 1992.
Complexity Zoo : IP, MIP Archived 2013-06-03 at the Wayback Machine , IPP Archived 2013-06-03 at the Wayback Machine , QIP Archived 2014-03-14 at the Wayback Machine , QIP(2) Archived 2014-03-14 at the Wayback Machine , compIP Archived 2013-05-21 at the Wayback Machine , frIP Archived 2013-06-03 at the Wayback Machine

[1] Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N. (1990). 「対話型証明システムのための代数的手法」. Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science . IEEE Comput. Soc. Press. pp. 2– 10. doi :10.1109/fscs.1990.89518. ISBN 0-8186-2082-X. S2CID 32614901。

[2] シャミール、アディ。「Ip= pspace」ACMジャーナル39.4（1992）：869-877。

[3] Chang Richard; et al. (1994). 「ランダムオラクル仮説は誤りである」. Journal of Computer and System Sciences . 49 (1): 24– 39. doi : 10.1016/s0022-0000(05)80084-4 .

[4] Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis (1989). 「対話型証明システムにおける完全性と健全性について」. Advances in Computing Research: A Research Annual . 5 : 429–442 . CiteSeerX 10.1.1.39.9412 . {{cite journal}}: CS1 maint: multiple names: authors list (link)

[5] R. Chang、B. Chor、Oded Goldreich、J. Hartmanis、J. Håstad、D. Ranjan、および P. Rohatgi。ランダムオラクル仮説は誤りです。ジャーナルオブコンピュータおよびシステムサイエンス、49(1):24-39。 1994年。

[6] J. Watrous. PSPACEは定数ラウンドの量子インタラクティブ証明システムを持つ. IEEE FOCS'99論文集, pp. 112-119. 1999.

[7] ラーフル・ジェイン;鄭峰季;サルヴァギャ・ウパディヤイ。ジョン・ワトラス(2009)。「QIP = PSPACE」。arXiv : 0907.4737 [quant-ph]。

[8] A. KitaevとJ. Watrous. 量子対話型証明システムの並列化、増幅、指数時間シミュレーション.第32回ACM計算理論シンポジウム論文集、pp. 608-617. 2000.

[9] シャフィ・ゴールドワッサーとミヒル・ベラーレ。意思決定と検索の複雑さ。SIAM Journal on Computing、第 23 巻、第 1 号、1994 年 2 月。

[10] ^ Cai JY, Threlfall RA (2004). 「二次残差と UPに関する注記」.情報処理レター. 92 (3): 127– 131. CiteSeerX 10.1.1.409.1830 . doi :10.1016/j.ipl.2004.06.015.

v t e 複雑度クラス
実現可能と考えられる	ログタイム AC ⁰ ACC ⁰ TC TC ⁰ L SL RL フロリダ州オランダ NL完全ノースカロライナ州 SC CC P P完全 ZPP RP BPP BQP APX FP
実行不可能と疑われる	上 NP NP完全 NP困難共同NP 共NP完全 TFNP FNP 午前 QMA PH ⊕P PP #P #P完了 IP Pスペース PSPACE完全版
実現不可能とみなされる	有効期限ネクスタイムエクスプスペース 2-EXPTIME 初等非初等広報 R 再エネ全て
その他の複雑性クラス	ポリL QP
クラス階層	多項式階層指数階層グジェゴルチク階層算術階層ブール階層
クラスのファミリー	Dタイム NTIME DSPACE Nスペース確率的に検証可能な証明インタラクティブな証明システム
複雑性クラスのリスト