Sistema de prueba interactivo

La clase de complejidad NP puede considerarse un sistema de prueba muy simple. En este sistema, el verificador es una máquina determinista de tiempo polinomial (una máquina P ). El protocolo es:

• El probador examina la entrada, calcula la solución utilizando su poder ilimitado y devuelve un certificado de prueba de tamaño polinomial.
• El verificador comprueba que el certificado sea válido en tiempo polinomial determinista. Si es válido, lo acepta; de lo contrario, lo rechaza.

En caso de existir un certificado de prueba válido, el probador siempre podrá lograr que el verificador lo acepte entregándole dicho certificado. Sin embargo, si no existe un certificado de prueba válido, la entrada no está en el idioma especificado, y ningún probador, por muy malintencionado que sea, podrá convencer al verificador de lo contrario, ya que cualquier certificado de prueba será rechazado.

Aunque NP puede considerarse que utiliza la interacción, no fue hasta 1985 que el concepto de computación a través de la interacción fue concebido (en el contexto de la teoría de la complejidad) por dos grupos de investigadores independientes. Un enfoque, el de László Babai , quien publicó "Intercambiando la teoría de grupos por la aleatoriedad" ^{[ 2 ]} , definió la jerarquía de clases Arthur-Merlin ( AM ). En esta presentación, Arthur (el verificador) es una máquina probabilística de tiempo polinomial, mientras que Merlin (el probador) tiene recursos ilimitados.

La clase MA en particular es una generalización simple de la interacción NP anterior en la que el verificador es probabilístico en lugar de determinista. Además, en lugar de requerir que el verificador siempre acepte certificados válidos y rechace certificados inválidos, es más indulgente:

• Completitud: si la cadena está en el lenguaje, el probador debe poder dar un certificado tal que el verificador lo acepte con una probabilidad de al menos 2/3 (dependiendo de las elecciones aleatorias del verificador).
• Solidez: si la cadena no pertenece al lenguaje, ningún probador, por muy malicioso que sea, podrá convencer al verificador de que acepte la cadena con una probabilidad superior a 1/3.

Esta máquina es potencialmente más potente que un protocolo de interacción NP ordinario , pero los certificados no son menos prácticos de verificar, ya que los algoritmos BPP se consideran como una abstracción de la computación práctica (véase BPP ).

En un protocolo de moneda pública , las elecciones aleatorias realizadas por el verificador se hacen públicas. En un protocolo de moneda privada, permanecen privadas.

En la misma conferencia donde Babai definió su sistema de prueba para MA , Shafi Goldwasser , Silvio Micali y Charles Rackoff ^{[ 3 ]} publicaron un artículo que define el sistema de prueba interactivo IP [ f ( n )]. Este tiene las mismas máquinas que el protocolo MA , excepto que se permiten f ( n ) rondas para una entrada de tamaño n . En cada ronda, el verificador realiza un cálculo y pasa un mensaje al probador, y el probador realiza un cálculo y pasa información de vuelta al verificador. Al final, el verificador debe tomar su decisión. Por ejemplo, en un protocolo IP [3], la secuencia sería VPVPVPV, donde V es el turno del verificador y P es el turno del probador.

En los protocolos Arthur-Merlin, Babai definió una clase similar, AM [ f ( n )], que permitía f ( n ) rondas, pero añadió una condición a la máquina: el verificador debía mostrar al probador todos los bits aleatorios que utilizaba en su cálculo. El resultado es que el verificador no puede ocultar nada al probador, ya que este último es lo suficientemente potente como para simular todo lo que hace el verificador si conoce los bits aleatorios que utiliza. Esto se denomina protocolo de moneda pública , porque los bits aleatorios ("lanzamientos de moneda") son visibles para ambas máquinas. En cambio, el enfoque IP se denomina protocolo de moneda privada .

El problema fundamental de las monedas públicas radica en que, si el probador pretende convencer maliciosamente al verificador de que acepte una cadena que no pertenece al lenguaje, parece que el verificador podría frustrar sus planes si logra ocultarle su estado interno. Esta fue una de las principales motivaciones para definir los sistemas de prueba de propiedad intelectual .

En 1986, Goldwasser y Sipser ^{[ 4 ]} demostraron, quizás sorprendentemente, que la capacidad del verificador para ocultar los lanzamientos de moneda al probador resulta poco útil, ya que un protocolo de moneda pública Arthur-Merlin con solo dos rondas más puede reconocer los mismos idiomas. El resultado es que los protocolos de moneda pública y privada son aproximadamente equivalentes. De hecho, como Babai demostró en 1988, AM [ k ] = AM para todo k constante , por lo que IP [ k ] no tiene ninguna ventaja sobre AM . ^{[ 5 ]}

Para demostrar el poder de estas clases, consideremos el problema del isomorfismo de grafos , que consiste en determinar si es posible permutar los vértices de un grafo de manera que sea idéntico a otro. Este problema pertenece a NP , ya que el certificado de prueba es la permutación que hace que los grafos sean iguales. Resulta que el complemento del problema del isomorfismo de grafos, un problema co- NP que no se sabe que pertenezca a NP , tiene un algoritmo AM y la mejor manera de verlo es mediante un algoritmo de monedas privadas. ^{[ 6 ]}

Las monedas privadas pueden no ser útiles, pero más rondas de interacción sí lo son. Si permitimos que la máquina de verificación probabilística y el probador todopoderoso interactúen durante un número polinomial de rondas, obtenemos la clase de problemas llamada IP . En 1992, Adi Shamir reveló en uno de los resultados centrales de la teoría de la complejidad que IP es igual a PSPACE , la clase de problemas resolubles por una máquina de Turing determinista ordinaria en espacio polinomial. ^{[ 7 ]}

Si permitimos que los elementos del sistema utilicen computación cuántica , el sistema se denomina sistema de prueba interactiva cuántica , y la clase de complejidad correspondiente se denomina QIP . ^{[ 8 ]} Una serie de resultados culminó en un avance en 2010 que demostró que QIP = PSPACE . ^{[ 9 ] [ 10 ]}

Los sistemas de prueba interactivos no solo pueden resolver problemas que no se consideran NP , sino que, bajo supuestos sobre la existencia de funciones unidireccionales , un probador puede convencer al verificador de la solución sin proporcionarle información alguna sobre ella. Esto es importante cuando no se puede confiar en que el verificador conozca la solución completa. Al principio, parece imposible que el verificador pueda convencerse de que existe una solución sin haber visto un certificado, pero se cree que tales pruebas, conocidas como pruebas de conocimiento cero, existen para todos los problemas de NP y son valiosas en criptografía . Las pruebas de conocimiento cero se mencionaron por primera vez en el artículo original de 1985 sobre IP de Goldwasser, Micali y Rackoff para lenguajes específicos de teoría de números. Sin embargo, el alcance de su poder fue demostrado por Oded Goldreich , Silvio Micali y Avi Wigderson para todo NP , ^{[ 6 ]} y Russell Impagliazzo y Moti Yung lo extendieron por primera vez a todo IP . ^{[ 11 ]}

Uno de los objetivos de los diseñadores de IP era crear el sistema de prueba interactiva más potente posible, y al principio parecía que no se podía hacer más potente sin hacer que el verificador fuera más potente y, por lo tanto, poco práctico. Goldwasser et al. superaron esto en su artículo de 1988 "Pruebas interactivas con múltiples probadores: cómo eliminar las suposiciones de intratabilidad", que define una variante de IP llamada MIP en la que hay dos probadores independientes. ^{[ 12 ]} Los dos probadores no pueden comunicarse una vez que el verificador ha comenzado a enviarles mensajes. Así como es más fácil saber si un criminal está mintiendo si él y su cómplice son interrogados en habitaciones separadas, es considerablemente más fácil detectar a un probador malicioso que intenta engañar al verificador para que acepte una cadena que no pertenece al lenguaje si hay otro probador con el que pueda realizar una doble verificación.

De hecho, esto es tan útil que Babai, Fortnow y Lund pudieron demostrar que MIP = NEXPTIME , la clase de todos los problemas resolubles por una máquina no determinista en tiempo exponencial , una clase muy grande. ^{[ 13 ]} NEXPTIME contiene PSPACE, y se cree que contiene estrictamente PSPACE. Agregar un número constante de probadores adicionales más allá de dos no permite el reconocimiento de más lenguajes. Este resultado allanó el camino para el célebre teorema PCP , que puede considerarse una versión "reducida" de este teorema.

MIP también posee la útil propiedad de que las pruebas de conocimiento cero para cada lenguaje en NP pueden describirse sin la suposición de funciones unidireccionales que IP debe hacer. Esto tiene relevancia en el diseño de algoritmos criptográficos demostrablemente irrompibles. ^{[ 12 ]} Además, un protocolo MIP puede reconocer todos los lenguajes en IP en solo un número constante de rondas, y si se agrega un tercer probador, puede reconocer todos los lenguajes en NEXPTIME en un número constante de rondas, demostrando nuevamente su poder sobre IP .

Se sabe que para cualquier constante k , un sistema MIP con k probadores y un número polinomial de rondas puede transformarse en un sistema equivalente con solo 2 probadores y un número constante de rondas. ^{[ 14 ]}

Mientras que los diseñadores de IP consideraron generalizaciones de los sistemas de prueba interactivos de Babai, otros consideraron restricciones. Un sistema de prueba interactivo muy útil es PCP ( f ( n ), g ( n )), que es una restricción de MA donde Arthur solo puede usar f ( n ) bits aleatorios y solo puede examinar g ( n ) bits del certificado de prueba enviado por Merlin (esencialmente usando acceso aleatorio ).

Existen varios resultados fáciles de comprobar sobre las distintas clases de PCP .${\displaystyle {\mathsf {PCP}}(0,{\mathsf {poly}})}$La clase de máquinas de tiempo polinomial sin aleatoriedad pero con acceso a un certificado es simplemente NP .${\displaystyle {\mathsf {PCP}}({\mathsf {poly}},0)}$⁠ , la clase de máquinas de tiempo polinomial con acceso a una cantidad polinomial de bits aleatorios es co- RP . El primer resultado importante de Arora y Safra fue que ⁠${\displaystyle {\mathsf {PCP}}(\log ,\log )={\mathsf {NP}}}$⁠ ; dicho de otra manera, si el verificador en el protocolo NP está restringido a elegir solo ⁠${\displaystyle O(\log n)}$⁠ partes del certificado de prueba para revisar, esto no hará ninguna diferencia siempre y cuando tenga ⁠${\displaystyle O(\log n)}$⁠ bits aleatorios para usar. ^{[ 15 ]}

Además, el teorema PCP afirma que el número de accesos a pruebas se puede reducir hasta un valor constante. Es decir ,${\displaystyle {\mathsf {NP}}={\mathsf {PCP}}(\log ,O(1))}$⁠ . ^{[ 16 ]} Utilizaron esta valiosa caracterización de NP para demostrar queno existen algoritmos de aproximación para las versiones de optimización de ciertos problemas NP-completos a menos que P = NP . Estos problemas se estudian ahora en el campo conocido como dificultad de aproximación .