MA (Complexitat)

En teoria de la complexitat, la classe de complexitat MA és el conjunt dels problemes de decisió que poden ser resolts en temps polinòmic per un protocol Arthur-Merlin d'un sol missatges. Només hi ha un missatge: Merlin envia un missatge a Arthur i aquest decideix si accepta o no executant un computació probabilística en temps polinòmic. En aquesta classe Merlín no té accés als resultats dels llançaments de moneda d'Arthur, ja que fa el llançament després de rebre el missatge de Merlin.

Per tant, un llenguatge L és a MA si existeix una màquina de Turing determinista de temps polinòmic M i uns polinomis p i q tals que per cada cadena d'entrada x de longitud n = |x|,

• 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{\forall }z\in \{0,1{\}}^{q(n)}\mathrm{Pr}{\mathrm{\backslash nolimits}}_{y\in \{0,1{\}}^{p(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{\forall }z\in \{0,1{\}}^{q(n)}\mathrm{Pr}{\mathrm{\backslash nolimits}}_{y\in \{0,1{\}}^{p(n)}}(M(x,y,z)=1)\le 1/3.$

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

Relació amb d'altres classes

La classe MA està contingut dins de les classes AM i QMA.

No se sap si les classes MA i AM son diferents, segons certes condicions les dues son equivalents a la classe NP.

MA conté les classes NP i BPP.