対話証明としての定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/14 08:31 UTC 版)
「Arthur–Merlinプロトコル」の記事における「対話証明としての定義」の解説
証明者(Prover, P)を無限の計算能力を持つチューリングマシン、検証者(Verifier, V)を確率的多項式時間チューリングマシンとする。PとVは互いに通信可能であり、P→Vの通信と、V→Pの通信をそれぞれ1-moveと数え、合わせて1ラウンドの対話と呼ぶ。Vは自分の持つランダムテープによって挙動が確率的となるが、このテープをV→Pの通信の際に送る。PとVは同一の入力xに対して、k-moveの通信後、Vが受理(accept)したとき、チューリングマシンのペア(P,V)(x)はxを受理するとする。次の条件を満たすとき、言語Lに対するAM[k](V→Pから始めた場合。P→Vから始めた場合はMA[k])対話プロトコルを構成しているといい、言語LはAM[k](あるいはMA[k])に属する。 (完全性 completeness) x ∈ L {\displaystyle x\in L} ならば、 Pr ( ( P , V ) ( x ) accepts ) ≥ 2 / 3 {\displaystyle \Pr((P,V)(x){\mbox{ accepts}})\geq 2/3} (健全性 soundness) x ∉ L {\displaystyle x\not \in L} ならば、 ∀ P ∗ Pr ( ( P ∗ , V ) ( x ) accepts ) ≤ 1 / 3 {\displaystyle \forall P^{*}\Pr((P^{*},V)(x){\mbox{ accepts}})\leq 1/3}
※この「対話証明としての定義」の解説は、「Arthur–Merlinプロトコル」の解説の一部です。
「対話証明としての定義」を含む「Arthur–Merlinプロトコル」の記事については、「Arthur–Merlinプロトコル」の概要を参照ください。
- 対話証明としての定義のページへのリンク
