AM / MA und NP in Analogie zu P und BPP

Arora und Barak zeigen, dass als ausgedrückt werden kann . ist auch eine natürliche randomisierte Verallgemeinerung von indem Sie den deterministischen Verifizierer durch einen randomisierten ersetzen.$\mathsf{AM}$M A N $\mathsf{BP}\cdot \mathsf{NP}$$\mathsf{MA}$$\mathsf{NP}$

Gibt es einen Sinn, in dem einer von diesen enger in das "P ist zu BPP wie NP ist zu" passt? Beziehung?

Dies ist natürlich eine sehr subjektive Angelegenheit, aber hier könnte man so interpretieren, dass eine engere Übereinstimmung aufweist: Dieselben Annahmen, die implizieren, dass implizieren auch dies , aber es ist nicht bekannt, dass diese Annahmen implizieren . Außerdem impliziert die Annahme, dass , dass , aber es ist nicht bekannt, dass impliziert .P = B P P N P = M A N P = A M p r o m i s e P = p r o m i s e B P P P r o m i s e N P = p r o m i s e m A p r o m i $\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}$

Es gibt jedoch eine alternative Ansicht, die besagt, dass die nicht deterministische Variante von während die probabilistische Variante von . Die vorstehenden Tatsachen können auch als Beweis für diese Auffassung gedeutet werden.$\mathbf{MA}$$\mathbf{BPP}$$\mathbf{AM}$$\mathbf{NP}$

Hier ist ein Punkt für AM: Für eine Komplexitätsklasse C ist fast-C die Menge von Sprachen, die sich in C relativ zu fast jedem Orakel befinden (fast = Wahrscheinlichkeit 1). Dann ist fast-P = BPP und fast-NP = AM.

In einer anderen Sichtweise ist IP die Verallgemeinerung, wenn Sie NP als das betrachten, was Sie einem Polynom-Zeit-Skeptiker beweisen können.