Arthur-Merlin-Protokoll

Question

Ich habe kürzlich über das Arthur-Merlin-Protokoll gelernt, und wir haben die Komplexitätsklassen $ AM, MA $ definiert.

Wir haben auch gesehen, dass es einen Theorem gibt, der angibt, dass der $ Amamam ... AM= AM $ , jedoch haben wir jedoch nicht förmlich definiert $ Amamamam ... am $ .

Wir haben eine kurze Definition für ihn als Protokoll gegeben, aber ich würde gerne eine formale Definition ohne Protokolle sehen , genau wie $ AM $ und $ MA $ (und $ mam $ )

Eine Definition für $ AMA $ sollte für mich ausreichen, nur um den Hang von zu bekommen, wie es aussehen soll.

danke!

Answer 1

$ AMA $ ist im Wesentlichen ein 3-runder interaktives Proof-System, in dem der Verifizierer (Arthur) nur Zufälligkeit an den Vorsprung (Merlin) senden darf.
. Ich habe noch keine explizite Definition gesehen, aber ich denke, wir können es wie folgt formulieren. Die erste Runde von AM [3] beginnt mit Merlin Senden einer Nachricht $ M_1 $ nach Arthur. In der zweiten Runde sendet Arthur Zufälligkeit $ R $ in Merlin, in der die endgültige dritte Runde gefolgt ist, in der Merlin eine Nachricht $ m_2 $ . Arthur beschließt dann, mit deterministischer Polynom-Zeit-Verifizierer $ V $ zu akzeptieren / abzulehnen.

Ich denke, wir können die Klasse wie folgt definieren.
Definition: $ l ∈ AMA $ Wenn es einen poly-Zeit-deterministischen Algorithmus gibt, der $ V $ vorhanden ist so, dass:

.
• wenn $ x \ in l \; (| x |= n) $ dann $ \ existiert P. PR_ {r \ in \ {0,1 \} ^ {p (n)}} ^ linke (v (x, m_1, r, m_2)= 1 \ rechts) \ ge 2/3 $ wo $ \; m_1= p (x), \; m_2= p (x, r) $
• wenn $ X \ NOTIN L \; (| x |= n) $ dann $ \ FORALL P. PR_ {r \ in \ {0,1 \} ^ {p (n)}} ^ linke (v (x, m_1, r, m_2)= 1 \ rechts) \ le 1/3 $ wo $ \; m_1= p (x), \; m_2= p (x, r) $

Beachten Sie den Vorsprung $ P $ ist eine Funktion $ P: \ {0,1 \} ^ \ \ rightarrow \ {{0,1 \} ^ {q (n)} $ , wobei $ q (n) $ ein Polynom ist.

Siehe: Rechenkomplizität von Arora-Baraks Abschnitt 8.1.