Protocole Arthur-Merlin

Le plus simple de ces protocoles est celui où Merlin envoie un message à Arthur, et où Arthur décide alors d'accepter ou non en faisant un calcul probabiliste en temps polynomial. Cette définition est proche de celle de NP utilisant un vérificateur, à ceci près qu'Arthur est ici autorisé à utiliser de l'aléatoire. Merlin, dans ce protocole, n'a pas accès aux lancers de pièce d'Arthur, étant donné qu'il s'agit d'un protocole à un seul message, et qu'Arthur ne lance ses pièces qu'après avoir reçu le seul message de Merlin. Ce protocole est appelé le protocole MA. Informellement, un langage L appartient à MA si, pour tous mots du langage, il y a une preuve de taille polynomiale que Merlin peut envoyer à Arthur pour le convaincre avec une très forte probabilité de l'appartenance de ce mot à L, et pour tous les mots qui ne sont pas dans le langage, n'y a pas de preuve qui puisse convaincre Arthur avec une haute probabilité de l'appartenance à ce langage. Cependant, Arthur n'est pas forcément un vérificateur de BPP, car on ne sait pas si MA est contenu dans la classe ${\displaystyle \exists BPP}$[2].

Formellement, la classe de complexité MA est l'ensemble des problèmes de décision qui peuvent être décidés en temps polynomial par un protocole Arthur-Merlin, où le seul message de Merlin précède tout calcul d'Arthur. En d'autres termes, un langage L appartient à MA s'il existe une machine de Turing M déterministe fonctionnant en temps polynomial, et des polynômes p et q tels que pour toute entrée x de taille n = |x|,

• si x est dans L, alors ${\displaystyle \exists z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\geq 2/3,}$
• si x n'est pas dans L, alors ${\displaystyle \forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=0)\geq 2/3.}$

La seconde condition peut être également écrite sous la forme :

• si x n'est pas dans L, alors ${\displaystyle \forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\leq 1/3.}$

Pour faire le lien avec la définition informelle décrite ci-dessus, z est la soi-disant preuve donnée par Merlin (de taille polynomiale), et y est le mot aléatoire utilisé par Arthur, qui est aussi de taille polynomiale.

La classe de complexité AM (ou AM[2]) est l'ensemble des problèmes de décision qui peuvent être décidés en temps polynomial par un protocole d'Arthur et Merlin avec deux messages. Il n'y a qu'une paire de questions/réponses : Arthur lance des pièces aléatoires et envoie le résultat de tous ses lancers de pièces à Merlin, qui lui répond avec une soi-disant preuve, et Arthur vérifie la preuve de manière déterministe. Dans ce protocole, Arthur n'est autorisé qu'à envoyer à Merlin les résultats de ses lancers de pièces, et doit décider à la dernière étape d'accepter ou non en n'utilisant que les résultats de ses précédents lancers de pièces et le message de Merlin.

En d'autres termes, un langage L appartient à AM s'il existe une machine de Turing déterministe M en temps polynomial et des polynômes p et q tels que pour toute entrée x de longueur n = |x|,

• si x est dans L, alors ${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\geq 2/3,}$
• si x n'est pas dans L, alors ${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3.}$

La deuxième condition peut être réécrite sous la forme :

• si x n'est pas dans L, alors ${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.}$

De même que précédemment, z est la soi-disant preuve fournie par Merlin (de taille polynomiale), et y est le mot aléatoire qu'Arthur utilise, qui est aussi de taille polynomiale.

La classe de complexité AM[k] est l'ensemble des problèmes qui peuvent être décidés en temps polynomial, avec k questions et réponses. AM défini plus haut est AM[2]. AM[3] commencerait avec un message de Merlin à Arthur, puis un message d'Arthur à Merlin, et enfin un message de Merlin à Arthur. Le dernier message doit toujours être de Merlin à Arthur, étant donné qu'il ne sert de rien à Arthur d'envoyer un message à Merlin, qui n'aura jamais de réponse, avant de donner sa réponse.