AM / MA dan NP dalam analogi dengan P dan BPP

Arora dan Barak menunjukkan bahwa dapat dinyatakan sebagai B P ⋅ N P yaitu sekumpulan bahasa yang memiliki reduksi acak menjadi 3SAT. M A juga generalisasi acak alami N P dalam bahwa Anda mengganti verifier deterministik dengan satu acak.$\mathsf{AM}$$\mathsf{BP}\cdot \mathsf{NP}$$\mathsf{MA}$$\mathsf{NP}$

Apakah ada perasaan di mana salah satu dari ini lebih cocok dalam "P adalah untuk BPP seperti NP?" hubungan?

$\mathbf{MA}$$\mathbf{P} = \mathbf{BPP}$$\mathbf{NP} = \mathbf{MA}$$\mathbf{NP} = \mathbf{AM}$$\mathrm{promise}\mathbf{P} = \mathrm{promise}\mathbf{BPP}$$\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{MA}$$\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{AM}$

$\mathbf{MA}$$\mathbf{BPP}$$\mathbf{AM}$$\mathbf{NP}$

Inilah poin untuk AM: Untuk kelas kompleksitas C, hampir-C didefinisikan sebagai sekumpulan bahasa yang ada di C relatif terhadap hampir setiap oracle (hampir = Probabilitas 1). Kemudian hampir-P = BPP dan hampir-NP = AM.

Untuk melemparkan pandangan lain, IP adalah generalisasi jika Anda berpikir tentang NP sebagai apa yang dapat Anda buktikan kepada skeptis waktu polinomial.