Exiger l'unicité des réponses valides pour Merlin limite-t-il la puissance des protocoles Arthur-Merlin?

Préambule.

La classe de complexité AM sont les problèmes qui peuvent être résolus par un système de preuve interactif à deux tours entre un prouveur "Merlin" et un vérificateur "Arthur". Un problème - qui teste certaines propriétés d'un objet X - est dans AM si:

• Pour les instances OUI , pour un message de "défi" aléatoire (de longueur polynomiale) généré par Arthur, avec une forte probabilité Merlin peut formuler une réponse (longueur polynomiale) qu'Arthur peut utiliser comme preuve que X a la propriété;

• Pour AUCUN cas, pour un message aléatoire challenge Arthur génère, avec une forte probabilité Merlin ne peut formuler une réponse qui peut être utilisé comme preuve pour la propriété essayées sur X .

- La classe décrite ne change pas si nous demandons à Merlin de donner une réponse utile non seulement avec une forte probabilité, mais pour tout défi qu'Arthur peut lancer; nous pourrions dire dans ce cas que nous exigeons que la réponse de Merlin soit toujours valide pour les instances OUI , et ce qu'Arthur teste est la validité de la réponse. Donc, si Merlin produit une réponse invalide, Arthur sait que l'instance à problème est une instance NO . C'est le paramètre que je préfère considérer.

Un exemple est Graph Non-Isomorphism: étant donné les graphiques G et H avec le même ensemble d'étiquettes de sommet, Arthur peut sélectionner au hasard l'un des graphiques et produire une version F "brouillée" en permutant ses étiquettes de sommet, en envoyant une présentation à Merlin . Si les deux graphiques ne sont pas isomorphes, Merlin peut identifier lequel de G ou H Arthur a choisi en déterminant si F  ≅  G ou F  ≅  H , et peut répondre en identifiant lequel des deux F est isomorphe. Si les deux graphiques G et H sont isomorphes, cependant, Merlin ne peut pas distinguer quel graphiqueF vient de, et toute réponse qu'il donne ne peut être correcte que par hasard. Ainsi, pour les instances OUI , Merlin peut toujours envoyer une réponse valide à n'importe quel défi; Pour AUCUN cas, toute réponse que Merlin pourrait envoyer sera avec une probabilité élevée invalide.

Dans le problème ci-dessus, non seulement il existe une réponse valide que Merlin peut envoyer à Arthur pour chaque défi, mais en fait il y a une réponse valide unique : c.  -à- d. Indiquer laquelle de G ou H Arthur a choisi, étant donné que cela peut être déterminé par identification qui est isomorphe à F .

Question.

Est-ce que l'imposition d'une contrainte dans ce sens - que pour les instances OUI , pour tout défi qu'Arthur pourrait envoyer, il y a exactement une réponse valide pour Merlin - donne une classe plus restrictive, dans le sens de produire une classe qui n'est pas connue pour être égale à AM ?

$m$$n$$\mathbb{C}^n$$p$$H(p)=0$$H$$(a_0,a_1,\cdots, a_n)$$m$$\bmod p$

$\bmod p$$p$$\bmod p$$p$$p$

$p$$\mathbb{C}^n$$p$$a$$1-1/e$

Ainsi, dans le problème ci-dessus, non seulement il existe une réponse valide que Merlin peut envoyer à Arthur pour chaque défi, mais en fait il pourrait y avoir un grand nombre de réponses valides.

$p$$p$