AMに属する問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/14 08:31 UTC 版)
「Arthur–Merlinプロトコル」の記事における「AMに属する問題」の解説
グラフ非同型問題(Graph Non-Isomorphism problem, GNI)は、2つのグラフ G 0 , G 1 {\displaystyle G_{0},G_{1}} が与えられたとき、同型でないことを判定する問題である。GNIは、AMに属する。具体的なAMプロトコルを構成するよりも、IP[const]プロトコルを構成した方が分かりやすい。 検証者はランダムに b ∈ { 0 , 1 } {\displaystyle b\in \{0,1\}} 、 π ∈ S n {\displaystyle \pi \in {S_{n}}} を選び、 π ( G b ) {\displaystyle \pi (G_{b})} を証明者に送る。 証明者は、 π ( G b ) = G b ~ {\displaystyle \pi (G_{b})=G_{\tilde {b}}} となるような b ~ ∈ { 0 , 1 } {\displaystyle {\tilde {b}}\in \{0,1\}} を検証者に送る。 検証者は、 b ~ = b {\displaystyle {\tilde {b}}=b} ならば受理し、そうでなければ拒否する。 上記のプロトコルは、IP[const]プロトコルである。2つのグラフが非同型のとき検証者は必ず受理し、同型のときどんな証明者でも検証者は1/2の確率で拒否する。
※この「AMに属する問題」の解説は、「Arthur–Merlinプロトコル」の解説の一部です。
「AMに属する問題」を含む「Arthur–Merlinプロトコル」の記事については、「Arthur–Merlinプロトコル」の概要を参照ください。
- AMに属する問題のページへのリンク
