AM (Complexitat)

En teoria de la complexitat, la classe de complexitat AM (també coneguda per AM[2]) és el conjunt dels problemes de decisió que poden ser resolts en temps polinòmic per un protocol Arthur-Merlin de dos missatges. Només hi ha un parell pregunta/resposta: Arthur llança unes monedes i envia tots els resultats a Merlin, Merlin respon i Arthur decideix si accepta o no. Cal que

• Si la resposta és SI, llavors Merlin pot actuar de manera que Arthur accepti amb probabilitat d'almenys 2/3
• Si la resposta és NO, llavors faci el que faci Merlin, Arthur rebutja amb probabilitat d'almenys 2/3.

Es pot reformular la definició de la següent manera: un llenguatge L és a AM si existeix una màquina de Turing determinista en temps polinòmic i els polinomis p i q tals que:

• si x és a L, llavors $\mathrm{Pr}{\mathrm{\backslash nolimits}}_{y\in \{0,1{\}}^{p(n)}}(\mathrm{\exists }z\in \{0,1{\}}^{q(n)}M(x,y,z)=1)\ge 2/3$
• si x no és a L, llavors $\mathrm{Pr}{\mathrm{\backslash nolimits}}_{y\in \{0,1{\}}^{p(n)}}(\mathrm{\forall }z\in \{0,1{\}}^{q(n)}M(x,y,z)=0)\ge 2/3$

La segona condició es pot escriure d'aquesta forma alternativa:

• si x no és a L, llavors $\mathrm{Pr}{\mathrm{\backslash nolimits}}_{y\in \{0,1{\}}^{p(n)}}(\mathrm{\exists }z\in \{0,1{\}}^{q(n)}M(x,y,z)=1)\le 1/3$

z és la prova que envia Merlin (de mida polinòmica) i y és la cadena aleatòria que envia Arthur, que també està fitada polinòmicament.

El problema de saber si dos grafs no son isomorfs pertany a aquesta classe.

Relació amb d'altres classes

La classe AM[k] és la classe de problemes resolts en temps polinòmic, amb k preguntes i respostes. La definició anterior correspon a AM[2]. Per qualsevol k>2 la classe AM[k] és igual a AM[2]. Si k es pot relacionar de manera polinòmica amb la mida de l'entrada, la classe AM[poly(n)] és igual a la classe IP, que es coneix que és igual a PSPACE i es creu fermament que és més potent que la classe AM[2].

Se sap que si AM conté co-NP, llavors PH = AM.

La classe AM conté les classes NP, BPP i SZX.

També es coneix que per tot k, $AM[k]\subseteq IP[k]\subseteq AM[k+2]$.