Ist

Ich konnte in der Literatur keine Aussage zu $\mathsf{MA}$ und $\mathsf{NP}^\mathsf{RP}$ ; Hinweise wären willkommen.

Ich glaube, sie sind gleich:

• $\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$ : Die$\mathsf{NP}$ Maschine errät Merlins Saite, und das$\mathsf{RP}$ Orakel überprüft die Saite wie Arthur.

• : Merlin schätzt die akzeptierende Berechnung der N P- Maschine, einschließlich aller Anrufe, sowie die Ergebnisse dieser Anrufe an das R P- Orakel. Arthur dann überprüftdass die Berechnung gültigund dass alle die vermuteten Ergebnisse der Anrufe an den R P Orakel korrekt waren. Er verwendet Verstärkungs- und Vereinigungsgrenzen, um die gesamte Fehlerwahrscheinlichkeit zu begrenzen.$\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$$\mathsf{NP}$$\mathsf{RP}$$\mathsf{RP}$

Ist das richtig?

In der ersten Kugel brauchen wir das Orakel, um zu antworten

• $1$

• $\le 1/2$

$\mathrm{MA}\subseteq\mathrm{NP}^{\mathrm{promiseRP}}$