¿Es

No he podido encontrar una declaración que relacione y N P R P en la literatura; los punteros serían apreciados$\mathsf{MA}$$\mathsf{NP}^\mathsf{RP}$

Creo que son iguales:

• : El N P máquina adivina cadena de Merlin, y los R P verifica Oracle la cadena como Arthur haría.$\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$$\mathsf{NP}$$\mathsf{RP}$

• : Merlin adivina el cálculo de aceptación de lamáquina N P , incluidas todas las llamadas, así como los resultados de estas llamadas, aloráculo R P. Arthur luego verifica que el cálculo es válido y que todos los resultados adivinados de las llamadas aloráculo de R P fueron correctos. Utiliza amplificación y límites de unión para limitar la probabilidad total de error total.$\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$$\mathsf{NP}$$\mathsf{RP}$$\mathsf{RP}$

¿Es esto correcto?

En la primera viñeta, necesitaríamos el oráculo para responder

• $1$

• $\le 1/2$

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