Protocole Arthur-Merlin

Question

J'ai récemment appris sur le protocole Arthur-Merlin et nous avons défini les classes de complexité $ am, ma $ .

.

Nous avons également vu qu'il existe un théorème indiquant que $ amamam ... am= am $ , mais nous n'avons pas formellement défini $ amamamam ... am $ .

Nous avons donné une brève définition pour cela en tant que protocole, mais j'aimerais voir une définition formelle sans protocoles , comme $ am $ et $ ma $ (et $ mam $

)

une définition pour $ AMA $ devrait suffire pour moi, juste pour avoir le pendentif de la façon dont il devrait regarder.

merci!

Answer 1

$ AMA $ est essentiellement un système d'épreuve interactif à 3 ronds où le vérificateur (Arthur) est autorisé à envoyer au prouveur (Merlin).
Je n'ai pas encore vu une telle définition explicite, mais je pense que nous pouvons le formuler comme suit. Le premier tour d'AM [3] commence par Merlin envoi d'un message $ m_1 $ à Arthur. Au second tour, Arthur envoie au hasard $ r $ à Merlin, suivi du troisième cycle final dans lequel Merlin envoie un message $ m_2 $ . Arthur décide ensuite d'accepter / de rejeter à l'aide de vérificateur de temps polynomial déterministe $ V $ .

Je pense que nous pouvons définir la classe comme suit.
Définition: $ l ∈ AMA $ S'il existe un algorithme déterministe poly-temps $ v tel que:

• si $ x \ in l \; (| x |= n) $ thin $ \ Existe P. pr_ {r \ in \ \ \ \ {0,1 \} ^ {p (n)}} \ gone (v (x, m_1, r, m_2)= 1 \ droite) \ ge 2/3 $ Où $ \; m_1= p (x), \; m_2= p (x, r) $
• si $ x \ notin l \; (| x |= n) $ alors $ \ Forall P. pr_ {r \ in \ \ \ \ \ {0,1 \} ^ {p (n)}} \ gauche (v (x, m_1, r, m_2)= 1 \ droite) \ Le 1/3 $ Où $ \; m_1= p (x), \; m_2= p (x, r) $

NOTEZ LE PROVER $ P $ est une fonction $ P: \ {0,1 \} ^ \ RightArw \ {0,1 \} ^ {q (n)} $ , où $ q (n) $ est un polynôme.

Voir: Complexité de calcul de l'article 8.1 de Arora-Barak.