Arthur-Merlinプロトコル

Question

最近、Arthur-Merlinプロトコルについて学んで、複雑さクラス $ am、ma $ を定義しました。

$ AMAMAM ... AM= AM $ であることを示す定理が存在することもありますが、正式に定義されていません $ amamamam ... am $ 。

私たちはそれをプロトコルとして簡潔な定義をしましたが、 $ am $ <のように、プロトコルなしで正式な定義を見たいです。/ span>と $ MA $ （および $ mam $ ）

$ AMA $ の定義は、それがどのように見えるかのハングを手に入れるためだけで十分です。

ありがとう！

Answer 1

$ AMA $ は、基本的に検証者（Arthur）がプラバー（Merlin）にランダム性を送信することを許可されている3ラウンドインタラクティブプルーフシステムです。
私はそのような明示的な定義をまだ見たことがありませんが、私たちは次のようにそれを策定できると思います。 AM [3]の最初のラウンドは、MerlinからMerlinを送信します。 $ m_1 $ をArthurに送信します。 2番目のラウンドでは、Arthurはrandomness $ r $ をmerlinに送信します。これは、Merlinがメッセージを送信する最後の3番目のラウンドが続く $ m_2 $ 。次に、Arthurは、決定論的多項式 - 時間検証者 $ V $ を使用して受け入れる/拒否を決定します。

次のようにクラスを定義できると思います。
定義： $ L∈AMA $ $ v $が存在する場合

$ x \;（| X |= n）$ $ \ exists p.pr_ {r \ in \ {0,1 \} ^ {p（n）}} \ left（v（x、m_1、r、m_2）= 1 \ right）\ GE 2/3 $ class="math-container"> $ \; M_1= P（x）、\; M_2= P（x、r）$ $ x \ notin l \;（| X |= n）$ $ \ forall p.pr_ {r \ in \ in {0,1 \} ^ {p（n）}} \ left（v（x、m_1、r、m_2）= 1 \ right）\ LE 1/3 $ $ \; M_1= P（x）、\; M_2= P（x、r）$

注文 $ p $ は関数 $ p：\ {0,1 \} ^ * \ requirearrowです。 \ {0,1 \} ^ {q（n）} $ 。 $ q（n）$ は多項式です。

aorora-barakのセクション8.1による計算補完率。