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] Es requereix 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 $\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 $\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 $\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 modifica

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, $AM[k]\subseteq IP[k]\subseteq AM[k+2]$ .^[1]

Referències modifica

↑ ^1,0 ^1,1 Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.
↑ 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, 1988-04, pàg. 254–276. DOI: 10.1016/0022-0000(88)90028-1. ISSN: 0022-0000.

[:0-1] 1,0 ^1,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, 1988-04, pàg. 254–276. DOI: 10.1016/0022-0000(88)90028-1. ISSN: 0022-0000.

[1]

[2]