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.[1][2]

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
  • si x no és a L, llavors

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

  • si x no és a L, llavors

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

modifica

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.[3]

MA conté les classes NP i BPP.

Referències

modifica
  1. Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
  2. «Complexity Zoo:M - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-10-16. [Consulta: 3 desembre 2018].
  3. Impagliazzo, Russell; Wigderson, Avi «P = BPP if E requires exponential circuits: derandomizing the XOR lemma». Proceeding STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 04-05-1997, pàg. 220–229. DOI: 10.1145/258533.258590.