Est

Je n'ai pas pu trouver de déclaration reliant $\mathsf{MA}$ et $\mathsf{NP}^\mathsf{RP}$ dans la littérature; des pointeurs seraient appréciés.

Je pense qu'ils sont égaux:

• $\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$ : Lamachine$\mathsf{NP}$ devine la chaîne de Merlin, et l'oracle$\mathsf{RP}$ vérifie la chaîne comme Arthur le ferait.

• $\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$ : Merlin devine le calcul acceptant de lamachine$\mathsf{NP}$ , y compris tous les appels, ainsi que les résultats de ces appels, vers l'oracle$\mathsf{RP}$Arthur vérifie alors que le calcul est valide et que tous les résultats devinés des appels au$\mathsf{RP}$oracle R P étaient corrects. Il utilise des limites d'amplification et d'union pour délimiter la probabilité totale d'erreur globale.

Est-ce correct?

Dans la première puce, nous aurions besoin de l'oracle pour répondre

• OUI, si le test d'Arthur réussit avec probabilité $1$ (en supposant que le protocole MA est parfaitement complet),

• NON, si le chèque de Arthur réussit avec une probabilité .$\le 1/2$

Cela ressemble à un algorithme coRP, mais le problème est qu'il n'y a aucune garantie que l'une de ces deux conditions s'applique à chaque entrée possible dans l'oracle. Ainsi, l'oracle ne calcule pas une CoRP langue , mais un CoRP problème de promesse , et l'argumentation montre seulement que .$\mathrm{MA}\subseteq\mathrm{NP}^{\mathrm{promiseRP}}$