.svg/1280px-Interactive_proof_(complexity).svg.png)
En la teoría de la complejidad computacional , un sistema de prueba interactivo es una máquina abstracta que modela la computación como el intercambio de mensajes entre dos partes: un probador y un verificador . Las partes interactúan intercambiando mensajes para determinar si una cadena dada pertenece a un lenguaje o no. El probador posee recursos computacionales ilimitados pero no es confiable, mientras que el verificador tiene un poder computacional limitado pero se supone que siempre es honesto. Los mensajes se envían entre el verificador y el probador hasta que el verificador tiene una respuesta al problema y se ha "convencido" a sí mismo de que es correcta.
Todos los sistemas de prueba interactivos tienen dos requisitos:
La naturaleza específica del sistema, y por lo tanto la clase de complejidad de los lenguajes que puede reconocer, depende de qué tipo de límites se le imponen al verificador, así como de las capacidades que se le otorgan; por ejemplo, la mayoría de los sistemas de prueba interactivos dependen críticamente de la capacidad del verificador para tomar decisiones aleatorias. También depende de la naturaleza de los mensajes intercambiados: cuántos y qué pueden contener. Se ha descubierto que los sistemas de prueba interactivos tienen algunas implicaciones importantes para las clases de complejidad tradicionales definidas utilizando solo una máquina. Las principales clases de complejidad que describen los sistemas de prueba interactivos son AM e IP .
Cada sistema de prueba interactivo define un lenguaje formal de cadenas . La solidez del sistema de prueba se refiere a la propiedad de que ningún demostrador puede hacer que el verificador acepte la afirmación incorrecta excepto con una pequeña probabilidad. El límite superior de esta probabilidad se conoce como el error de solidez de un sistema de prueba. Más formalmente, para cada demostrador y cada :
para algunos . Mientras el error de solidez esté limitado por una fracción polinómica del tiempo de ejecución potencial del verificador (es decir, ), siempre es posible amplificar la solidez hasta que el error de solidez se vuelva una función despreciable en relación con el tiempo de ejecución del verificador. Esto se logra repitiendo la prueba y aceptando solo si todas las pruebas verifican. Después de las repeticiones, un error de solidez se reducirá a . [1]
La clase de complejidad NP puede considerarse un sistema de prueba muy simple. En este sistema, el verificador es una máquina de tiempo polinomial determinista (una máquina P ). El protocolo es:
En el caso de que exista un certificado de prueba válido, el verificador siempre podrá hacer que el verificador lo acepte entregándole dicho certificado. Sin embargo, en el caso de que no exista un certificado de prueba válido, la entrada no está en el lenguaje y ningún verificador, por malintencionado que sea, podrá convencer al verificador de lo contrario, porque cualquier certificado de prueba será rechazado.
Aunque se puede considerar que la NP 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 independientes de investigadores. Un enfoque, de László Babai , quien publicó "Trading group theory for randomness" [2] , definió la jerarquía de clases Arthur–Merlin ( AM ). En esta presentación, Arthur (el verificador) es una máquina de tiempo polinomial probabilística , 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 exigir que el verificador siempre acepte certificados válidos y rechace certificados no válidos, es más indulgente:
Esta máquina es potencialmente más poderosa que un protocolo de interacción NP ordinario , y los certificados no son menos prácticos de verificar, ya que los algoritmos BPP se consideran como una abstracción del cálculo práctico (ver 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 el cálculo y pasa un mensaje al probador, y el probador realiza el cálculo y pasa la 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 un turno del verificador y P es un turno del probador.
En los protocolos Arthur-Merlin, Babai definió una clase similar AM [ f ( n )] que permitía f ( n ) rondas, pero puso una condición adicional en la máquina: el verificador debe mostrar al probador todos los bits aleatorios que utiliza en su cálculo. El resultado es que el verificador no puede "ocultar" nada al probador, porque el probador es lo suficientemente poderoso como para simular todo lo que hace el verificador si sabe qué bits aleatorios utilizó. Esto se llama protocolo de moneda pública , porque los bits aleatorios ("lanzamientos de moneda") son visibles para ambas máquinas. El enfoque IP se llama, en cambio, protocolo de moneda privada .
El problema esencial de las monedas públicas es que si el verificador desea convencer maliciosamente al verificador de que acepte una cadena que no está en el lenguaje, parece que el verificador podría frustrar sus planes si puede ocultarle su estado interno. Esta fue una motivación principal para definir los sistemas de prueba de propiedad intelectual .
En 1986, Goldwasser y Sipser [4] demostraron, quizás de manera sorprendente, que la capacidad del verificador de ocultar los lanzamientos de moneda al probador no le sirve de mucho después de todo, ya que un protocolo de moneda pública Arthur-Merlin con solo dos rondas más puede reconocer todos los mismos idiomas. El resultado es que los protocolos de moneda pública y de moneda privada son aproximadamente equivalentes. De hecho, como muestra Babai en 1988, AM [ k ] = AM para todas las constantes k , por lo que los IP [ k ] no tienen ninguna ventaja sobre AM . [5]
Para demostrar el poder de estas clases, considere el problema de isomorfismo de grafos , el problema de determinar si es posible permutar los vértices de un grafo de modo que sea idéntico a otro grafo. Este problema está en NP , ya que el certificado de prueba es la permutación que hace que los grafos sean iguales. Resulta que el complemento del problema de isomorfismo de grafos, un problema co- NP que no se sabe que esté en NP , tiene un algoritmo AM y la mejor manera de verlo es a través de 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 verificadora probabilística y el probador todopoderoso interactúen durante un número polinómico 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 que se pueden resolver mediante una máquina de Turing determinista ordinaria en el espacio polinómico. [7]
Si permitimos que los elementos del sistema utilicen computación cuántica , el sistema se denomina sistema de prueba interactivo cuántico y la clase de complejidad correspondiente se denomina QIP . [8] Una serie de resultados culminó en un avance en 2010 de que QIP = PSPACE . [9] [10]
Los sistemas de prueba interactivos no sólo pueden resolver problemas que no se cree que estén en NP , sino que, bajo suposiciones sobre la existencia de funciones unidireccionales , un probador puede convencer al verificador de la solución sin darle nunca información sobre la solución. Esto es importante cuando no se puede confiar en el verificador con la solución completa. Al principio parece imposible que el verificador pueda convencerse de que hay una solución cuando el verificador no ha visto un certificado, pero se cree que tales pruebas, conocidas como pruebas de conocimiento cero , existen de hecho para todos los problemas en 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 teóricos de números específicos. Sin embargo, el alcance de su poder fue demostrado por Oded Goldreich , Silvio Micali y Avi Wigderson [ 6] para todo NP , y esto fue extendido por primera vez por Russell Impagliazzo y Moti Yung a todo IP [11] .
Uno de los objetivos de los diseñadores de IP era crear el sistema de prueba interactivo más potente posible, y al principio parece que no se puede hacer más potente sin hacer que el verificador sea más potente y, por lo tanto, poco práctico. Goldwasser et al. superaron esto en su artículo de 1988 "Multi prover interactive proofs: How to remove intratable budgets" (Pruebas interactivas de múltiples probadores: cómo eliminar los supuestos de intractabilidad), 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 compañero 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 está en el lenguaje si hay otro probador con el que puede hacer 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 que puede resolver una máquina no determinista en tiempo exponencial , una clase muy grande. [13] NEXPTIME contiene PSPACE, y se cree que contiene estrictamente a 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 tiene la propiedad útil de que las pruebas de conocimiento cero para cada idioma en NP se pueden describir sin la suposición de funciones unidireccionales que IP debe realizar. Esto tiene relación con el diseño de algoritmos criptográficos demostrablemente inquebrantables. [12] Además, un protocolo MIP puede reconocer todos los idiomas en IP en solo un número constante de rondas, y si se agrega un tercer demostrador, puede reconocer todos los idiomas en NEXPTIME en un número constante de rondas, lo que demuestra 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 se puede convertir 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 ).
Hay una serie de resultados fáciles de probar sobre varias clases de PCP . , la clase de máquinas de tiempo polinomial sin aleatoriedad pero con acceso a un certificado, es simplemente NP . , 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 ; dicho de otra manera, si el verificador en el protocolo NP está restringido a elegir solo bits del certificado de prueba para mirar, esto no hará ninguna diferencia mientras tenga bits aleatorios para usar. [15]
Además, el teorema PCP afirma que el número de accesos a la prueba se puede reducir hasta una constante. Es decir, . [16] Utilizaron esta valiosa caracterización de NP para demostrar que no existen algoritmos de aproximación para las versiones de optimización de ciertos problemas NP-completos a menos que P = NP . Dichos problemas se estudian ahora en el campo conocido como dureza de aproximación .
![{\displaystyle \Pr[(\perp ,({\text{aceptar}}))\obtiene ({\tilde {\mathcal {P}}})(y)\leftrightarrow ({\mathcal {V}})(y)]<\epsilon .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89775f36bd79764d20bcbb10051edc1470cf8baa)
