¿Exigir unicidad de respuestas válidas para Merlin limita el poder de los protocolos Arthur-Merlin?

Preámbulo.

La clase de complejidad AM son aquellos problemas que pueden resolverse mediante un sistema de prueba interactivo de dos rondas entre un probador "Merlin" y un verificador "Arthur". Un problema, que prueba alguna propiedad de un objeto X , está en AM si:

• Para casos de SÍ , para un mensaje aleatorio de "desafío" (de longitud polinómica) que Arthur genera, con alta probabilidad Merlín puede formular una respuesta (longitud polinómica) que Arthur puede usar como evidencia de que X tiene la propiedad;

• Para NO casos, para un mensaje de desafío aleatoria Arthur genera, con alta probabilidad Merlin no puede formular cualquier respuesta que se puede utilizar como evidencia de la propiedad que está siendo probado para en X .

- La clase descrita no cambia si le pedimos a Merlín que brinde una respuesta útil no solo con alta probabilidad, sino para cualquier desafío que Arthur pueda emitir; podríamos decir en este caso que exigimos que la respuesta de Merlín sea siempre válida para las instancias SÍ , y lo que Arthur prueba es la validez de la respuesta. Entonces, si Merlín alguna vez produce una respuesta no válida, Arthur sabe que la instancia del problema es una instancia NO . Esta es la configuración que preferiría considerar.

Un ejemplo es Graph Non-Isomorphism: dados los gráficos G y H con el mismo conjunto de etiquetas de vértice, Arthur puede seleccionar aleatoriamente uno de los gráficos y producir una versión F "codificada" al permutar sus etiquetas de vértice, enviando una presentación a Merlin . Si las dos gráficas no son isomorfas, Merlín puede identificar cuál de G o H eligió Arthur determinando si F  ≅  G o F  ≅  H , y puede responder identificando cuál de las dos F es isomorfa. Sin embargo, si las dos gráficas G y H son isomorfas, Merlín no puede distinguir qué gráficaF vino, y cualquier respuesta que dé solo puede ser correcta por casualidad. Por lo tanto, para casos de SÍ , Merlín siempre puede enviar una respuesta válida a cualquier desafío; para ninguna instancia, cualquier respuesta que Merlín pueda enviar será inválida con alta probabilidad.

En el problema anterior, no solo existe una respuesta válida que Merlín puede emitir a Arthur para cada desafío, sino que de hecho hay una respuesta válida única : es decir,  indicar cuál de G o H eligió Arthur, dado que esto puede determinarse por identificar que es isomorfo a F .

Pregunta.

¿Imponer una restricción a lo largo de estas líneas, que para casos de SÍ , para cualquier desafío que Arthur pueda enviar, hay exactamente una respuesta válida para Merlín, produce una clase más restrictiva, en el sentido de producir una clase que no se sabe que es igual a AM ?

El artículo de Koiran, Nullstellensatz de Hilbert está en la Jerarquía Polinómica, proporciona un protocolo Arthur-Merlin de moneda pública para establecer que un sistema de $m$ ecuaciones en $n$ incógnitas tiene una solución en $\mathbb{C}^n$ , dependiendo de la Hipótesis de Riemann Generalizada. Aquí, Merlín encuentra un $p$ primo con $H(p)=0$ para algún hash aleatorio $H$ , junto con una solución $(a_0,a_1,\cdots, a_n)$ para cada una de las ecuaciones $m$$\bmod p$

Si el sistema de ecuaciones no tiene solución , entonces solo habrá un número finito de módulo que existe una solución. Si el sistema lo hace tener una solución , entonces incondicionalmente habrá una densidad positiva de con una solución, y la GRH permite que el con una solución son "equidistributed" en cierto sentido, de modo que Merlin consigue una victoria.$\bmod p$$p$mod p p p$\bmod p$$p$$p$

Aunque Koiran da un ejemplo de un sistema solucionable donde la densidad de es exponencialmente pequeña, Koiran sugiere que si el sistema se puede resolver en , en la mayoría de los casos habrá un gran número de (y un gran número de ); de hecho, aproximadamente primos deberían tener una solución IIRCC.$p$$\mathbb{C}^n$ p a 1 - 1 / e$p$$a$$1-1/e$

Por lo tanto, en el problema anterior, no solo existe una respuesta válida que Merlín puede emitir a Arthur para cada desafío, sino que de hecho podría haber una gran cantidad de respuestas válidas.

Distinguir los sistemas fáciles de ecuaciones con soluciones módulo muchos de los sistemas duros de ecuaciones con pocas o solo una parece requerir propiedades determinantes de un grupo de Galois del sistema de ecuaciones.$p$$p$