En teoria de la complexitat, la classe de complexitat AM (també coneguda per AM) é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 si x no és a L, llavors

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

si x no és a L, llavors

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. Per qualsevol k>2 la classe AM[k] és igual a AM. 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.

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, .

Referències

Categoria:Classes de complexitat