Protocolo Arthur-Merlin

En la teoría de complejidad computacional, un protocolo Arthur–Merlin es un sistema de prueba interactivo en el que los lanzamientos de monedas del verificador están obligados a ser públicos (es decir, también conocidos por el probador). Esta noción fue introducida por Babai (1985).Goldwasser y Sipser (1986) demostraron que todos los lenguajes formales con pruebas interactivas de longitud arbitraria con monedas privadas también tienen pruebas interactivas con monedas públicas.

Dados dos participantes en el protocolo llamado Arthur y Merlin respectivamente, la suposición básica es que Arthur es una computadora estándar (o verificador) equipada con un dispositivo generador de números aleatorios, mientras que Merlin es efectivamente un oráculo con un poder computacional infinito (también conocido como prover); pero Merlin no es necesariamente honesto, por lo que Arthur debe analizar la información proporcionada por Merlin en respuesta a las preguntas de Arthur y decidir el problema en sí. Un problema se considera que es solucionable mediante este protocolo si cada vez que la respuesta es "sí", Merlin tiene alguna serie de respuestas que hará que Arthur para aceptar al menos 2/3 de las veces y si cada vez que la respuesta es "no", Arthur nunca aceptará más de 1/3 del tiempo. Por lo tanto, Arthur actúa como un verificador probabilístico de tiempo polinómico, suponiendo que se le asigna tiempo polinómico para tomar sus decisiones y consultas.

MA

El protocolo más simple es el protocolo de 1 mensaje donde Merlin le envía a Arthur un mensaje y luego Arthur decide si acepta o no ejecutando un cálculo de tiempo polinomial probabilístico. (Esto es similar a la definición de NP basada en verificador, la única diferencia es que a Arthur se le permite usar aleatoriedad aquí.) Merlín no tiene acceso a los lanzamientos de monedas de Arthur en este protocolo, ya que es un protocolo de mensaje único y Arthur lanza sus monedas solo después de recibir el mensaje de Merlin. Este protocolo se llama MA. Informalmente, un lenguaje L está en MA si para todas las cadenas en el idioma, hay una prueba de tamaño polinómico de que Merlín puede enviar a Arthur para convencerlo de este hecho con alta probabilidad, y para todas las cadenas que no están en el idioma no hay prueba de que convence a Arthur con alta probabilidad.

Formalmente, la clase de complejidad MA es el conjunto de problemas de decisión que se pueden decidir en tiempo polinómico mediante un protocolo Arthur-Merlin donde el único movimiento de Merlin precede a cualquier cálculo por parte de Arthur. En otras palabras, un lenguaje L está en MA si existe una máquina de Turing determinista de tiempo polinómico M y polinomios p, q tal que para cada cadena de entrada x de longitud n = | x |,

• si x está en L, entonces $\exists z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\geq 2/3,$
• si x no está en L, entonces $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=0)\geq 2/3.$

La segunda condición se puede escribir alternativamente como

• si x no está en L, entonces $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\leq 1/3.$

Para comparar esto con la definición informal anterior, z es la supuesta prueba de Merlín (cuyo tamaño está delimitado por un polinomio) e y es la cadena aleatoria que usa Arthur, que también está polinomialmente delimitada.

AM

La clase de complejidad AM (o AM[2]) es el conjunto de problemas de decisión que se pueden decidir en tiempo polinómico mediante un protocolo Arthur – Merlin con dos mensajes. Solo hay un par de consulta/respuesta: Arthur lanza algunas monedas al azar y envía el resultado de todos sus lanzamientos de monedas a Merlin, Merlin responde con una supuesta prueba, y Arthur verifica determinísticamente la prueba. En este protocolo, a Arthur solo se le permite enviar resultados de lanzamiento de monedas a Merlin, y en la etapa final Arthur debe decidir si acepta o rechaza utilizando solo sus lanzamientos aleatorios de monedas generados previamente y el mensaje de Merlin.

En otras palabras, un lenguaje L está en AM si existe una máquina de Turing determinista de tiempo polinomial M y polinomios p, q tal que para cada cadena de entrada x de longitud n = | x |,

• si x está en L, entonces $\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 está en L, entonces $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3.$

La segunda condición aquí puede reescribirse como

• si x no está en L, entonces $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.$

Como se indicó anteriormente, z es la supuesta prueba de Merlín (cuyo tamaño está limitado por un polinomio) e y es la cadena aleatoria que usa Arthur, que también está limitada polinomialmente.

La clase de complejidad AM[k] es el conjunto de problemas que se pueden decidir en tiempo polinómico, con k consultas y respuestas. AM como se definió anteriormente es AM [2]. AM [3] comenzaría con un mensaje de Merlin a Arthur, luego un mensaje de Arthur a Merlin y finalmente un mensaje de Merlin a Arthur. El último mensaje siempre debe ser de Merlín a Arthur, ya que nunca ayuda a Arthur enviarle un mensaje a Merlín después de decidir su respuesta.

Propiedades

Relaciones conocidas de MA y AM con otras clases de complejidad. Una flecha de la clase A a la clase B significa que A es un subconjunto de B.

• Tanto MA como AM permanecen sin cambios si sus definiciones se cambian para requerir completitud perfecta, lo que significa que Arthur acepta con una probabilidad de 1 (en lugar de 2/3) cuando x está en el lenguaje​
• Para cualquier constante k ≥ 2, la clase AM[k] es igual a AM[2]. Si k puede relacionarse polinomialmente al tamaño de la entrada, la clase AM[poly(n)] es igual a la clase IP, la cual es conocida por ser igual a PSPACE y se cree ampliamente que es más fuerte que la clase AM[2].
• MA está contenida en AM, dado que AM[3] contiene MA: Arthur puede, después de recibir el certificado de Merlin, cambiar el número requerido de monedas, enviarlas a Merlin e ignorar la respuesta.
• No se sabe a ciencia cierta si AM y MA son diferentes. Bajo límites inferiores del circuito plausible (similares a aquellos que implican que P=BPP), son iguales a NP.​
• AM es lo mismo que la clase BP.NP donde BP denota el operador probabilístico de error acotado. Además $\exists .{\mathsf {BPP}}$ (también escrito como ExistsBPP) es un subconjunto de MA. Si MA es igual a $\exists .{\mathsf {BPP}}$ es una pregunta abierta.
• La conversión de un protocolo privado de monedas, en el cual Merlin no puede predecir el resultado de las decisiones aleatorias de Arthur, incrementará el número de rondas de interacción por a lo sumo 2 en el caso general. Así que la versión de monedas privada de AM es igual a la versión de monedas públicas.
• MA contiene a NP y a BPP. Para BPP esto es inmediato, desde que Arthur puede simplemente ignorar a Merlin y resolver el problema directamente; para NP, Merlin necesita solo enviar a Arthur un certificado, el cual Arthur puede validar determinísticamente en tiempo polinomial.
• Tanto MA como AM están contenidos en la jerarquía polinomial. En particular, MA está contenido en la intersección de Σ₂^P y Π₂^P y AM está contenido en Π₂^P. Inclusive, MA está contenido en la subclase SP
  2,​ una clase de complejidad que expresa "alternancia simétrica". Ésta es una generalización del teorema de Sipser-Lautemann.
• AM está contenido en NP/poly, la clase de problemas de decisión computables en un tiempo polinomial no determinístico con un consejo polinómico de tamaño 0. La prueba es una variación del Teorema de Adleman's.
• MA está contenido en PP; este resultadod se debe a Vereshchagin.​
• MA está contenido en su versión cuántica QMA.​
• AM contiene el problema de decidir si dos grafos no son isomórficos. El protocolo usando monedas privadas es el siguiente y puede ser transformado a un protocolo de monedas públicas. Dados dos grafos G y H, Arthur elige arbitrariamente uno de ellos y elige una permutación aleatoria de sus vértices, presentado el grafo permutado l a Merlin. Merlin debe responder si I fue creado desde G o H. Si los grafos son no isomórficos, Merlin será capaz de responder con total certeza (comprando si I es isomórfico a G). Sin embargo, si los grafos son isomórficos, es posible que tanto G o H hayan sido (con la misma probabilidad) usados para crear I. En este caso, Merlin no tiene manera de distinguirlos y puede convencer a Arthur con probabilidad de a lo sumo 1/2, y esto puede ser amplificado a 1/4 por repetición. Esta es de hecho una prueba de conocimiento cero.
• Si AM contiene coNP entonces PH = AM. Esto es evidencia de que el isomorfismo de grafo es poco probablmente NP-completo, desde que esto implicaría el colapso de la jerarquía polinómica.
• Se conoce, asumiendo ERH, que para cualquier d el problema "Dada una colección de polimonios multivariados $f_{i}$ con cada coeficiente entero y de grado de a lo sumo d, tienen ellos en común un 0 complejo?" está en AM.​

Bibliografía

• Babai, László (1985), «Trading group theory for randomness», STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM, pp. 421-429, ISBN 978-0-89791-151-1 . Babai, László (1985), «Trading group theory for randomness», STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM, pp. 421-429, ISBN 978-0-89791-151-1 . .
• Goldwasser, Shafi; Sipser, Michael (1986), «Private coins versus public coins in interactive proof systems», STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, ACM, pp. 59-68, ISBN 978-0-89791-193-1 . Goldwasser, Shafi; Sipser, Michael (1986), «Private coins versus public coins in interactive proof systems», STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, ACM, pp. 59-68, ISBN 978-0-89791-193-1 . .
• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4 . Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4 . .
• Curso MIT de Madhu Sudán sobre complejidad avanzada

Enlaces externos

• Complexity Zoo: MA (en inglés)
• Complexity Zoo: AM (en inglés)

• Datos: Q4800823