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.[1] 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 ${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\geq 2/3}$
• si x no és a L, llavors ${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3}$

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

• si x no és a L, llavors ${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 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].[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, ${\displaystyle AM[k]\subseteq IP[k]\subseteq AM[k+2]}$.[1]

Referències

1. Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
2. Babai, László; Moran, Shlomo «Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes». Journal of Computer and System Sciences, 36, 2, 4-1988, pàg. 254–276. DOI: 10.1016/0022-0000(88)90028-1. ISSN: 0022-0000.