Protocole Arthur-Merlin

En théorie de la complexité, un protocole Arthur-Merlin est un système de preuve interactive dans lequel on impose que les lancers de pièces du vérificateur soient publics (c'est-à-dire également connus du démonstrateur). Cette notion a été introduite par László Babai en 1985. Godwasser et Sipser ont prouvé en 1986 que tous les langages avec preuves interactives de longueur arbitraire avec aléatoire privé peuvent aussi être décidés par des preuves interactives avec aléatoire public.

Explications

On suppose ici qu'Arthur est un ordinateur normal (ou un vérifieur) équipé d'un générateur de nombres aléatoires, alors que Merlin est un oracle avec une capacité de calcul infini (aussi appelé prouveur). Cependant, Merlin n'est pas nécessairement honnête, Arthur doit donc analyser l'information que Merlin lui fournit en réponse à sa requête, et décider le problème lui-même. Un problème est considéré comme résoluble par ce protocole si, lorsque la réponse est « oui », Merlin donnera une série de réponses telles que Arthur acceptera au moins les 2/3 du temps, et lorsque la réponse est « non », Arthur n'acceptera pas plus d'une fois sur 3. Ainsi, Arthur se comporte comme un vérifieur probabiliste en temps polynomial, en supposant qu'Arthur dispose d'un temps polynomial pour faire ses décisions et ses requêtes.

MA

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 $\exists BPP$.

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 $\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 $\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 $\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.

AM

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 $\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 $\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 $\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.

Propriétés

• Les classes MA et AM restent inchangées si leurs définitions sont modifiées en exigeant une complétude parfaite, i.e. qu'Arthur accepte avec probabilité 1 (au lieu de 2/3) quand x est dans le langage.
• Pour tout k≥ 2, la classe AM[k] est identique à AM[2]. Si k peut varier de manière polynomiale en la taille de l'entrée, la classe AM[poly(n)] est une classe de complexité bien plus forte, IP, que l'on sait être égale à PSPACE.
• MA est incluse dans AM, étant donné que MA[3] = AM, et que Arthur peut, après avoir reçu le certificat de Merlin, lancer le nombre de pièces nécessaires, les envoyer à Merlin, et ignorer la réponse.
• La question de savoir si AM et MA sont deux classes différentes est ouverte. Sous des conditions similaires à celles impliquant P = BPP, elles sont toutes deux égales à NP.
• AM est égale à BP.NP, où BP désigne l'opérateur probabiliste à erreur bornée. De plus, $\exists .BPP$ (aussi noté ExistsBPP) est inclus dans MA. L'égalité de MA et $\exists .BPP$ est une question ouverte.
• Changer ces protocoles en des protocoles à aléatoire privé, dans lesquels Merlin ne peut pas prédire le résultat des lancers de pièces d'Arthur, fait augmenter le nombre de tours d'interaction d'au plus 2 dans le cas général. Ainsi, la version à aléatoire privé de AM est égale à la version à aléatoire public.
• MA contient NP et BPP. Ce résultat est immédiat en ce qui concerne BPP, étant donné qu'Arthur peut simplement ignorer la réponse de Merlin et résoudre directement le problème. Pour NP, Merlin n'a qu'à envoyer à Arthur un certificat, qu'Arthur peut valider de manière déterministe en temps polynomial.
• MA et AM sont inclus dans la hiérarchie polynomiale. En particulier, MA est contenue dans l'intersection de Σ₂^P et Π₂^P, et AM est inclus dans Π₂^P. De plus, MA est inclus dans la sous-classe ${\mathsf {S}}_{2}^{P}$, par une généralisation du théorème de Sipser-Gács-Lautemann.
• AM est incluse dans NP/poly, la classe des problèmes de décision décidables en temps polynomial non-déterministe, avec un conseil de taille polynomiale. La preuve est une variante du théorème d’Adleman.
• MA est inclus dans PP. Ce résultat est dû à Vereshchagin.
• MA est inclus dans sa version quantique, QMA.
• AM contient le problème consistant à décider si deux graphes ne sont pas isomorphes. Le protocole, qui utilise un aléatoire privé, est le suivant, et peut être transformé en un protocole à aléatoire public. Étant donnés deux graphes G et H, Arthur choisit au hasard l'un d'entre eux, et choisit une permutation aléatoire de ses sommets, et envoie le graphe permuté, I, à Merlin. Merlin doit deviner si I a été créé à partir de G ou de H. Si les graphes ne sont pas isomorphes, Merlin sera capable de répondre avec certitude (en vérifiant si I est isomorphe à G). Cependant, si les graphes sont isomorphes, il est aussi bien possible que G ou H ait été utilisé pour créer I, avec une probabilité identique. Dans ce cas, Merlin ne peut pas les différencier, et ne peut convaincre Arthur qu'avec une probabilité au plus 1/2, qui peut être portée à 1/4 en répétant le protocole. Il s'agit en fait d'une preuve à divulgation nulle de connaissance.
• Si AM contient coNP, alors PH = AM. Il est donc peu probable que le problème de l'isomorphisme de graphes soit NP-complet, étant donné que cela impliquerait l'effondrement de la hiérarchie polynomiale.
• On sait que, en supposant l'hypothèse de Riemann généralisée, que pour tout d le problème

Étant donné une collection de polynômes à plusieurs variables $f_{i}$ à coefficients entiers et de degré au plus 'd, ont-ils un zéro commun dans $\mathbb {C}$ ?

est dans AM.

Bibliographie

• Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 10 (« Protocoles interactifs »)

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Arthur-Merlin protocol » (voir la liste des auteurs).