Protocolo Arthur-Merlin

Sistema de prueba interactivo en la teoría de la complejidad computacional

En la teoría de la complejidad computacional , un 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.

Dados dos participantes en el protocolo llamados 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 poder computacional infinito (también conocido como probador). Sin embargo, Merlin no es necesariamente honesto, por lo que Arthur debe analizar la información proporcionada por Merlin en respuesta a las consultas de Arthur y decidir el problema por sí mismo. Un problema se considera solucionable por este protocolo si siempre que la respuesta sea "sí", Merlin tiene una serie de respuestas que harán que Arthur acepte al menos 2 ⁄ 3 de las veces, y si siempre que la respuesta sea "no", Arthur nunca aceptará más de 1 ⁄ 3 de las veces. Por lo tanto, Arthur actúa como un verificador de tiempo polinomial probabilístico, asumiendo que se le asigna un tiempo polinomial para tomar sus decisiones y consultas.

MAMÁ

El protocolo más simple de este tipo es el protocolo de 1 mensaje, en el que Merlín le envía un mensaje a Arturo, y luego Arturo decide si lo acepta o no ejecutando un cálculo de tiempo polinomial probabilístico. (Esto es similar a la definición basada en verificador de NP, la única diferencia es que Arturo puede usar aleatoriedad aquí). 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 . Informalmente, un lenguaje L está en MA si para todas las cadenas en el lenguaje, hay una prueba del tamaño de un polinomio de 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 prueba que convenza a Arturo con alta probabilidad.

Formalmente, la clase de complejidad MA es el conjunto de problemas de decisión que pueden resolverse en tiempo polinomial mediante 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 en 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á limitado por un polinomio) e y es la cadena aleatoria que usa Arthur, que también está limitada polinomialmente.

SOY

La clase de complejidad AM (o AM[2] ) es el conjunto de problemas de decisión que se pueden resolver en tiempo polinomial 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 moneda 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 lanzamientos de moneda a Merlin y, en la etapa final, Arthur debe decidir si acepta o rechaza utilizando solo sus lanzamientos de moneda 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 en 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í se puede reescribir como

• si x no 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)\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 resolver en tiempo polinomial, con k consultas y respuestas. AM, 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 debería ser de Merlín a Arturo, ya que nunca ayuda que Arturo envíe 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 inalterados si se modifican sus definiciones para exigir 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 relacionarse polinomialmente 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 : Arturo puede, después de recibir el certificado de Merlín, lanzar la cantidad requerida de monedas, enviárselas a Merlín e ignorar la respuesta.
• No está claro si AM y MA son diferentes. En virtud de límites inferiores de circuito plausibles (similares a los que implican que 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, ( también escrito como ExistsBPP ) es un subconjunto de MA . Si MA es igual a es una pregunta abierta. ${\displaystyle \exists \cdot {\mathsf {BPP}}}$ ${\displaystyle \exists \cdot {\mathsf {BPP}}}$
• 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 2 como máximo en el caso general. Por lo tanto, la versión de moneda privada de AM es igual a la versión de 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 manera 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ág.
  ₂, ^[3] una clase de complejidad que expresa "alternancia simétrica". Esta es una generalización del teorema de Sipser-Lautemann .
• AM está contenido en NP/poly , la clase de problemas de decisión computables en tiempo polinomial no determinista con un tamaño polinomial advice . La prueba es una variación del teorema de Adleman .
• MA está contenida en PP ; este resultado se debe a Vereshchagin. ^[4]
• MA está contenida 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 monedas públicas. 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 Merlín. Merlín tiene que responder si I fue creado a partir de G o H . Si los grafos no son isomorfos, Merlín podrá responder con total certeza (verificando si I es isomorfo a G ). Sin embargo, si los grafos son isomorfos, es posible que se haya utilizado G o H para crear I , e igualmente probable. En este caso, Merlín no tiene forma de distinguirlos y puede convencer a Arthur con una probabilidad de como máximo 1/2, y esto puede amplificarse a 1/4 por repetición. Esto es, de hecho, una prueba de conocimiento cero .
• Si AM contiene coNP entonces PH = AM . Esto es evidencia de que es poco probable que el isomorfismo de grafos sea NP-completo, ya que implica el colapso de la jerarquía polinómica.
• Se sabe, suponiendo ERH , que para cualquier d el problema "Dada una colección de polinomios multivariados cada uno con coeficientes enteros y de grado como máximo d , ¿tienen un cero complejo común?" está en AM . ^[6] ${\displaystyle f_{i}}$

Referencias

1. Para una demostración, véase Rafael Pass y Jean-Baptiste Jeannin (24 de marzo de 2009). "Lecture 17: Arthur-Merlin games, Zero-knowledge proofs" (PDF) . Consultado el 23 de junio de 2010 .
2. Impagliazzo, Russell; Wigderson, Avi (4 de mayo de 1997). P = BPP si E requiere circuitos exponenciales: desaleatorización del lema XOR . ACM. págs. 220–229. doi :10.1145/258533.258590. ISBN. 0897918886. Número de identificación del sujeto  18921599.
3. "La alternancia simétrica captura BPP" (PDF) . Ccs.neu.edu . Consultado el 26 de julio de 2016 .
4. Vereschchagin, NK (1992). "Sobre el poder de PP". [1992] Actas de la Séptima Conferencia Anual de Teoría de la Estructura en la Complejidad . pp. 138–143. doi :10.1109/sct.1992.215389. ISBN 081862955X.S2CID 195705029  .
5. Vidick, Thomas; Watrous, John (2016). "Pruebas cuánticas". Fundamentos y tendencias en informática teórica . 11 (1–2): 1–215. arXiv : 1610.01664 . doi :10.1561/0400000068. ISSN  1551-305X. S2CID  54255188.
6. "Curso: Álgebra y Computación". People.csail.mit.edu . Consultado el 26 de julio de 2016 .

Bibliografía

• 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 versus 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 del MIT sobre complejidad avanzada impartido por Madhu Sudan

Enlaces externos

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