Apakah

Saya belum dapat menemukan sebuah pernyataan yang berkaitan dan N P R P dalam literatur; pointer akan dihargai.$\mathsf{MA}$$\mathsf{NP}^\mathsf{RP}$

Saya percaya mereka setara:

• : The N P Mesin menebak tali Merlin, dan R P oracle memverifikasi string sebagai Arthur akan.$\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$$\mathsf{NP}$$\mathsf{RP}$

• : Merlin menebak perhitungan menerima dari N P mesin, termasuk semua panggilan, serta hasil dari panggilan ini, dengan R P oracle. Arthur kemudian memverifikasi bahwa perhitungan tersebut valid dan bahwa semua hasil yang menduga panggilan ke R P oracle benar. Dia menggunakan amplifikasi dan batas-batas serikat untuk mengikat probabilitas kesalahan total keseluruhan.$\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$$\mathsf{NP}$$\mathsf{RP}$$\mathsf{RP}$

Apakah ini benar?

Dalam peluru pertama, kita akan membutuhkan oracle untuk menjawab

• $1$

• $\le 1/2$

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