Arthur–Merlinプロトコル
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/26 22:12 UTC 版)
計算複雑性理論におけるArthur–Merlinプロトコル(Arthur–Merlin protocol)あるいは、Merlin–Arthurプロトコル(Merlin–Arthur protocol)は、検証者のコイン投げが公開されている(使用する乱数が証明者に知られている)タイプの対話型証明プロトコルである。そのようなプロトコルを持つ言語のクラスとして、AM及びMAがそれぞれ定義され、本項では主にこのクラスについて説明する。Babai (1985)によって導入された。
- ^ 由来は、アーサー王物語のアーサー王とマーリン
- ^ つまり、証明者もそれを知ることができる
- ^ IP
- ^ 例えば、AM[3]は、検証者→証明者、証明者→検証者、検証者→証明者というやりとりをするプロトコルを持つ言語クラス
- ^ BPP
- ^ NP
- ^ Π2p
- ^ 直ちにP≠NPが導かれる
- ^ co-AMはco-NPを包含するので、AM=co-AMならば、
- ^ Zachos & Furer (1987)
- ^ a b Goldreich, Mansour & Sipser (1987)
- ^ はn次対称群
- ^ a b Babai (1985)
- ^ ここで、証明者から与えられるw以外について、例えばw'についてPr[M(x,w',r)=1]がどうなるか何も条件を課しておらず、1/2となってもよいことに注意
- ^ Goldwasser & Sipser (1986)
- ^ Schöning (1989)
- ^ 戸田 (2001, p. 28)
[続きの解説]
「Arthur–Merlinプロトコル」の続きの解説一覧
- 1 Arthur–Merlinプロトコルとは
- 2 Arthur–Merlinプロトコルの概要
- 3 AMに属する問題
- 4 性質
- 5 参考文献
- 6 外部リンク
- Arthur–Merlinプロトコルのページへのリンク
