É

Não consegui encontrar uma afirmação relacionada a e N P R P na literatura; ponteiros seriam apreciados.$\mathsf{MA}$$\mathsf{NP}^\mathsf{RP}$

Eu acredito que eles são iguais:

• : O N P máquina suposições cadeia de Merlin, e os R P verifica da Oracle a cadeia como Arthur faria.$\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$$\mathsf{NP}$$\mathsf{RP}$

• $\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$ : Merlin adivinha o cálculo de aceitação damáquina$\mathsf{NP}$ , incluindo todas as chamadas, bem como os resultados dessas chamadas, para ooráculo$\mathsf{RP}$Arthur então verifica se o cálculo é válido e se todos os resultados estimados das chamadas para ooráculo$\mathsf{RP}$ estavam corretos. Ele usa limites de amplificação e união para limitar a probabilidade total total de erro.

Isso está correto?

Na primeira bala, precisaríamos do oráculo para responder

• $1$

• $\le 1/2$

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