Protocolo Arthur-Merlín

En la teoría de la complejidad computacional , el protocolo Arthur - Merlin , introducido por Babai (1985) , es un sistema de prueba interactivo en el que los lanzamientos de moneda del verificador están restringidos a ser públicos (es decir, conocidos también por el probador). 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.

Dado que en el protocolo participan dos personas llamadas Arthur y Merlin, respectivamente, se parte de la premisa de que Arthur es un ordenador estándar (o verificador) equipado con un generador de números aleatorios , mientras que Merlin es, en efecto, un oráculo con capacidad computacional infinita (también conocido como probador). Sin embargo, Merlin no es necesariamente honesto, por lo que Arthur debe analizar la información que Merlin proporciona en respuesta a sus consultas y resolver el problema por sí mismo. Un problema se considera resoluble mediante este protocolo si, siempre que la respuesta sea "sí", Merlin dispone de una serie de respuestas que harán que Arthur acepte la solución al menos dos tercios de las veces, y si, siempre que la respuesta sea "no", Arthur nunca la aceptará más de un tercio de las veces. Por lo tanto, Arthur actúa como un verificador probabilístico de tiempo polinomial, asumiendo que se le asigna un tiempo polinomial para tomar sus decisiones y realizar sus consultas.

El protocolo más simple de este tipo es el protocolo de un mensaje, donde Merlín envía un mensaje a Arturo, y luego Arturo decide si lo acepta o no mediante un cálculo probabilístico de tiempo polinomial. (Esto es similar a la definición de NP basada en verificadores, con la única diferencia de que aquí Arturo puede usar aleatoriedad). Merlín no tiene acceso a los lanzamientos de moneda de Arturo en este protocolo, ya que es un protocolo de un solo mensaje y Arturo lanza sus monedas solo después de recibir el mensaje de Merlín. Este protocolo se llama MA . De manera informal, un lenguaje L está en MA si para todas las cadenas del lenguaje, hay una prueba de tamaño polinomial que Merlín puede enviar a Arturo para convencerlo de este hecho con alta probabilidad, y para todas las cadenas que no están en el lenguaje no hay ninguna prueba que convenza a Arturo con alta probabilidad.

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

• Si x está en L , entonces${\displaystyle \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${\displaystyle \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 puede escribirse alternativamente como

• Si x no está en L , entonces${\displaystyle \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á acotado por un polinomio) e y es la cadena aleatoria que usa Arthur, que también está acotada polinómicamente.

La clase de complejidad AM (o AM[2] ) es el conjunto de problemas de decisión que pueden resolverse en tiempo polinomial mediante un protocolo Arthur - Merlin con dos mensajes. Existe un único par consulta/respuesta: Arthur lanza monedas al azar y envía el resultado de todos sus lanzamientos a Merlin, Merlin responde con una supuesta prueba y Arthur la verifica de forma determinista. En este protocolo, Arthur solo puede enviar los resultados de los lanzamientos a Merlin, y en la etapa final debe decidir si acepta o rechaza utilizando únicamente los resultados de sus lanzamientos aleatorios 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 tales que para cada cadena de entrada x de longitud n = | x |,

• Si x está en L , entonces${\displaystyle \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${\displaystyle \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${\displaystyle \Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall 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á acotado por un polinomio) e y es la cadena aleatoria que usa Arthur, que también está acotada polinómicamente.

La clase de complejidad AM[ k ] es el conjunto de problemas que pueden resolverse en tiempo polinomial, con k consultas y respuestas. AM, tal como se definió anteriormente, es AM[2] . AM[3] comenzaría con un mensaje de Merlín a Arturo, luego un mensaje de Arturo a Merlín y, finalmente, un mensaje de Merlín a Arturo. El último mensaje siempre debe ser de Merlín a Arturo, ya que nunca le sirve de nada a Arturo enviar un mensaje a Merlín después de haber decidido su respuesta.

• Tanto MA como AM permanecen sin cambios si sus definiciones se modifican para requerir una completitud perfecta, lo que significa que Arthur acepta con probabilidad 1 (en lugar de 2/3) cuando x está en el lenguaje. ^{[ 1 ]}
• Para cualquier constante k ≥ 2, la clase AM[ k ] es igual a AM[2] . Si k puede estar relacionado polinómicamente con el tamaño de entrada, la clase AM [poly( n )] es igual a la clase IP , que se sabe que es igual a PSPACE y se cree ampliamente que es más fuerte que la clase AM[2] .
• MA está contenido en AM , ya que AM [3] contiene MA : Arthur puede, después de recibir el certificado de Merlín, lanzar el número requerido de monedas, enviárselas a Merlín e ignorar la respuesta.
• Queda por determinar si AM y MA son diferentes. Bajo límites inferiores de circuitos plausibles (similares a los que implican P = BPP ), ambos son iguales a NP . ^{[ 2 ]}
• AM es lo mismo que la clase BP⋅NP donde BP denota el operador probabilístico de error acotado. Además,${\displaystyle \exists \cdot {\mathsf {BPP}}}$(también escrito como ExistsBPP ) es un subconjunto de MA . Si MA es igual a${\displaystyle \exists \cdot {\mathsf {BPP}}}$Es una cuestión abierta.
• La conversión a un protocolo de moneda privada, en el que Merlín no puede predecir el resultado de las decisiones aleatorias de Arturo, aumentará el número de rondas de interacción en un máximo de 2 en el caso general. Por lo tanto, la versión de AM con moneda privada es igual a la versión con moneda pública.
• MA contiene tanto NP como BPP . Para BPP, esto es inmediato, ya que Arthur puede simplemente ignorar a Merlin y resolver el problema directamente; para NP, Merlin solo necesita enviarle a Arthur un certificado, que Arthur puede validar de forma determinista en tiempo polinomial.
• Tanto MA como AM están contenidos en la jerarquía polinómica . En particular, MA está contenido en la intersección de Σ ₂ ^P y Π ₂ ^P , y AM está contenido en Π ₂ ^P. Más aún, MA está contenido en la subclase S ^P ₂ , ^{[ 3 ]} una clase de complejidad que expresa "alternancia simétrica". Esta es una generalización del teorema de Sipser-Lautemann .
• AM está incluido en NP/poly , la clase de problemas de decisión computables en tiempo polinomial no determinista con un consejo de tamaño polinomial . La demostración es una variación del teorema de Adleman .
• MA está contenido en PP ; este resultado se debe a Vereshchagin. ^{[ 4 ]}
• MA está contenido en su versión cuántica, QMA . ^{[ 5 ]}
• AM contiene el problema de decidir si dos grafos no son isomorfos. El protocolo que utiliza monedas privadas es el siguiente y puede transformarse en un protocolo de moneda pública. Dados dos grafos G y H , Arthur elige aleatoriamente uno de ellos y elige una permutación aleatoria de sus vértices, presentando el grafo permutado I a Merlin. Merlin tiene que responder si I fue creado a partir de G o H. Si los grafos no son isomorfos, Merlin podrá responder con total certeza (verificando si I es isomorfo a G ). Sin embargo, si los grafos son isomorfos, es posible que G o H se hayan utilizado para crear I , y es igualmente probable. En este caso, Merlin no tiene forma de distinguirlos y puede convencer a Arthur con una probabilidad máxima de 1/2, que puede amplificarse a 1/4 mediante repetición. De hecho, esta es una prueba de conocimiento cero .
• Si AM contiene coNP, entonces PH = AM . Esto demuestra que es improbable que el isomorfismo de grafos sea NP-completo, ya que implica el colapso de la jerarquía polinómica.
• Se sabe, asumiendo ERH , que para cualquier d el problema "Dado un conjunto de polinomios multivariados${\displaystyle f_{i}}$cada uno con coeficientes enteros y de grado como máximo d , ¿tienen un cero complejo común?" está en AM . ^{[ 6 ]}

• Babai, László (1985), "Intercambio de teoría de grupos por aleatoriedad", STOC '85: Actas del decimoséptimo simposio anual de la ACM sobre Teoría de la Computación , ACM, págs. 421–429 , ISBN  978-0-89791-151-1.
• Goldwasser, Shafi ; Sipser, Michael (1986), "Monedas privadas frente a monedas públicas en sistemas de prueba interactivos", STOC '86: Actas del decimoctavo simposio anual de la ACM sobre teoría de la computación , ACM, págs. 59-68 , ISBN  978-0-89791-193-1.
• Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional: un enfoque moderno , Cambridge , ISBN 978-0-521-42426-4.
• Curso de Madhu Sudan en el MIT sobre complejidad avanzada

• Zoológico de la complejidad : MA
• Zoológico de la complejidad : AM