AM / MA i NP analogicznie do P i BPP

Arora i Barak pokazują, że można wyrazić jako B P ⋅ N P, tj. Zestaw języków, w których losowe obniżki do 3SAT. M jest także naturalnym randomizowane uogólnienie N P w które zastąpi deterministyczny weryfikatora przez randomizowanym jeden.$\mathsf{AM}$$\mathsf{BP}\cdot \mathsf{NP}$$\mathsf{MA}$$\mathsf{NP}$

Czy istnieje sens, w którym jedno z nich jest ściślej dopasowane do „P oznacza BPP tak jak NP?”. związek?

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

Oto kwestia AM: w przypadku klasy złożoności C prawie-C jest definiowane jako zbiór języków, które są w C względem prawie każdej wyroczni (prawie = Prawdopodobieństwo 1). Następnie prawie-P = BPP i prawie-NP = AM.

Aby rzucić inny pogląd, IP jest uogólnieniem, jeśli myślisz o NP jako o tym, co możesz udowodnić sceptycznemu czasowi wielomianowemu.