Protocolo Arthur-Merlin - Arthur–Merlin protocol

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 monedas del verificador están obligados a ser públicos (es decir, también conocidos 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 prover ). Sin embargo, Merlín no es necesariamente honesto, por lo que Arthur debe analizar la información proporcionada por Merlín en respuesta a las consultas 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 ² / ₃ de las veces, y si cada vez que la respuesta es "no" , Arthur nunca aceptará más de ¹ / ₃ del tiempo. Por lo tanto, Arthur actúa como un verificador probabilístico de tiempo polinomial, asumiendo que se le asigna 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 envía un mensaje a Arthur, y luego Arthur decide si acepta o no mediante la ejecución de un cálculo de tiempo polinomial probabilístico. (Esto es similar a la definición de NP basada en el verificador, la única diferencia es que Arthur puede usar la 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 Merlín. Este protocolo se llama MA . De manera informal, un lenguaje L está en MA si para todas las cadenas en el idioma, hay una prueba de tamaño polinomial 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 mucha probabilidad.

Formalmente, la clase de complejidad MA es el conjunto de problemas de decisión que se pueden decidir 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 probabilística 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 \ existe 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 se puede escribir 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 utiliza Arthur, que también está acotada polinomialmente.

SOY

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. 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 Merlín, Merlín responde con una supuesta prueba y Arthur verifica determinísticamente la prueba. En este protocolo, Arthur solo puede enviar los resultados de los lanzamientos de monedas a Merlín, y en la etapa final Arthur debe decidir si acepta o rechaza utilizando solo sus lanzamientos de monedas aleatorios generados previamente y el mensaje de Merlín.

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)}} (\ existe 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)}} (\ existe z \ in \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 1) \ leq 1/3.}$

Como arriba, 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 polinomialmente.

La clase de complejidad AM [ k ] es el conjunto de problemas que se pueden decidir en tiempo polinomial, con k consultas y respuestas. AM como se define 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 Merlin a Arthur, ya que nunca ayuda a Arthur enviar un mensaje a Merlin 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 clase B significa A es un subconjunto de B .

• Tanto MA como AM permanecen sin cambios si sus definiciones se cambian para requerir una completitud perfecta, lo que significa que Arthur acepta con probabilidad 1 (en lugar de 2/3) cuando x está en el idioma.
• Para cualquier constante k ≥ 2, la clase AM [ k ] es igual a AM [2] . Si k puede estar relacionado polinomialmente con el tamaño de entrada, la clase AM [poli ( n )] es igual a la clase IP , que se sabe que es igual a PSPACE y se cree 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 Merlin, lanzar la cantidad requerida de monedas, enviarlas a Merlin e ignorar la respuesta.
• Está abierto si AM y MA son diferentes. Bajo límites inferiores de circuito plausibles (similares a los que implican P = BPP ), ambos 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, (también escrito como ExistsBPP ) es un subconjunto de MA . Si MA es igual a es una pregunta abierta. ${\ Displaystyle \ existe \ cdot {\ mathsf {BPP}}}$${\ Displaystyle \ existe \ cdot {\ mathsf {BPP}}}$
• La conversión a un protocolo de monedas privado, en el que Merlín no puede predecir el resultado de las decisiones aleatorias de Arthur, aumentará el número de rondas de interacción como máximo en 2 en el caso general. Entonces, la versión de moneda privada de AM es igual a la versión de moneda pública.
• MA contiene NP y BPP . Para BPP esto es inmediato, ya que Arthur puede simplemente ignorar a Merlín y resolver el problema directamente; para NP, Merlin solo necesita enviar 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 polinomial . En particular, MA está contenida en la intersección de Σ ₂ ^P y Π ₂ ^P y AM está contenida en Π ₂ ^P . Aún más, MA está contenido en la subclase S ^P
  ₂ , 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 calculables 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.
• MA está contenido en su versión cuántica, QMA .
• AM contiene el problema de decidir si dos gráficos no son isomorfos. El protocolo que utiliza monedas privadas es el siguiente y se puede transformar en un protocolo de monedas públicas. Dados dos gráficos G y H , Arthur elige aleatoriamente uno de ellos y elige una permutación aleatoria de sus vértices, presentando el gráfico permutado I a Merlín. Merlin tiene que responder si I fue creado de G o H . Si los gráficos no son isomórficos, Merlín podrá responder con total certeza (verificando si I es isomórfico a G ). Sin embargo, si las gráficas son isomórficas, es posible que se haya usado G o H para crear I , e igualmente probable. En este caso, Merlín no tiene forma de diferenciarlos y puede convencer a Arthur con una probabilidad de 1/2 como máximo, y esto puede amplificarse a 1/4 por repetición. De hecho, esta es 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 polinomial.
• Se sabe, asumiendo ERH , que para cualquier d el problema "Dada una colección de polinomios de múltiples variables, cada uno con coeficientes enteros y de grado como máximo d , ¿tienen un cero complejo común?" está en AM . ${\ Displaystyle f_ {i}}$

Referencias

Bibliografía

• Babai, László (1985), "Teoría de grupos comerciales para la aleatoriedad", STOC '85: Actas del decimoséptimo simposio anual de 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 ACM sobre teoría de la computación , ACM, págs. 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 .
• Curso MIT de Madhu Sudan sobre complejidad avanzada

enlaces externos

• Complejo zoológico : MA
• Complejidad Zoo : AM