AM / MA и NP по аналогии с P и BPP

Арора и Барак показывают, что можно выразить как B P ⋅ N P, то есть набор языков, которые имеют рандомизированные сокращения до 3SAT. M A также является естественным рандомизированным обобщением N P в том смысле, что вы заменяете детерминированный верификатор на рандомизированный.$\mathsf{AM}$$\mathsf{BP}\cdot \mathsf{NP}$$\mathsf{MA}$$\mathsf{NP}$

Есть ли смысл в том, что один из них ближе подходит к «P - к BPP, как NP к»? отношение?

$\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}$

Вот точка для AM: Для класса сложности C почти C определяется как набор языков, которые находятся в C относительно почти каждого оракула (почти = Вероятность 1). Тогда почти-P = BPP и почти-NP = AM.

Иными словами, IP - это обобщение, если вы думаете о NP как о том, что вы можете доказать скептику за полиномиальное время.