.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 determinada pertenece a un idioma o no. El probador posee recursos computacionales ilimitados pero no se puede confiar en él, mientras que el verificador tiene un poder de cálculo 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" de que es correcta.
Todos los sistemas de prueba interactivos tienen dos requisitos:
La naturaleza específica del sistema, y por 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 qué capacidades se le otorgan; por ejemplo, la mayoría de los sistemas de prueba interactivos dependen críticamente de la 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 una sola 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 probador puede hacer que el verificador acepte una afirmación incorrecta, excepto con una pequeña probabilidad. El límite superior de esta probabilidad se denomina error de solidez de un sistema de prueba. Más formalmente, para cada probador y cada :
para algunos . Siempre que 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 convierta en una función insignificante en relación con el tiempo de ejecución del verificador. Esto se logra repitiendo la prueba y aceptándola sólo si todas las pruebas se verifican. Después de las repeticiones, el error de solidez se reducirá a . [1]
La clase de complejidad NP puede verse como 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 probador siempre puede hacer que el verificador acepte entregándole ese certificado. Sin embargo, en el caso de que no exista un certificado de prueba válido, la entrada no está en el idioma y ningún probador, por malicioso que sea, puede 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 dos grupos independientes de investigadores concibieron (en el contexto de la teoría de la complejidad) el concepto de computación a través de la interacción. Un enfoque, de László Babai , quien publicó "Teoría de grupos comerciales para 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 polinómico, mientras que Merlín (el probador) tiene recursos ilimitados.
La clase MA en particular es una simple generalización 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 acepte siempre los certificados válidos y rechace los invá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 cálculos prácticos abstractos (ver BPP ).
En un protocolo de moneda pública , las elecciones aleatorias realizadas por el verificador se hacen públicas. Permanecen privados en un protocolo de moneda privado.
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 )]. 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 cálculos y pasa un mensaje al probador, y el probador realiza cálculos y pasa información 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 de verificación y P es un turno de prueba.
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 mostrarle 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 potente como para simular todo lo que hace el verificador si sabe qué bits aleatorios utilizó. A esto se le llama protocolo de moneda pública , porque los bits aleatorios ("lanzamientos de moneda") son visibles para ambas máquinas. Por el contrario, el enfoque IP se denomina protocolo de moneda privada .
El problema esencial con las monedas públicas es que si el probador desea convencer maliciosamente al verificador de que acepte una cadena que no está en el idioma, parece que el verificador podría frustrar sus planes si puede ocultarle su estado interno. Esta fue una motivación principal a la hora de definir los sistemas de prueba de propiedad intelectual .
En 1986, Goldwasser y Sipser [4] demostraron, tal vez sorprendentemente, que la capacidad del verificador para ocultar los lanzamientos de moneda al probador no sirve de mucho después de todo, en el sentido de que un protocolo público de monedas Arthur-Merlin con sólo dos rondas más puede reconocer todas las monedas. mismos idiomas. El resultado es que los protocolos de monedas públicas y privadas son aproximadamente equivalentes. De hecho, como muestra Babai en 1988, AM [ k ] = AM para toda k constante , por lo que los IP [ k ] no tienen ventaja sobre AM . [5]
Para demostrar el poder de estas clases, considere el problema del isomorfismo de grafos , el problema de determinar si es posible permutar los vértices de un grafo para que sea idéntico a otro grafo. Este problema está en NP , ya que el certificado de prueba es la permutación que iguala las gráficas. Resulta que el complemento del problema de isomorfismo gráfico, 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]
Puede que las monedas privadas no sean útiles, pero más rondas de interacción sí son útiles. Si permitimos que la máquina verificadora probabilística y el todopoderoso demostrador 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 pueden resolverse mediante una máquina determinista ordinaria de Turing en el espacio polinomial. [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 culminaron en un avance en 2010: QIP = PSPACE . [9] [10]
Los sistemas de prueba interactivos no solo 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 siquiera darle información sobre la solución. Esto es importante cuando no se puede confiar al verificador la solución completa. Al principio parece imposible que el verificador pueda estar convencido de que existe una solución cuando no ha visto un certificado, pero de hecho se cree que tales pruebas, conocidas como pruebas de conocimiento cero, existen 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 propiedad intelectual de Goldwasser, Micali y Rackoff para lenguajes específicos de teoría de números. Sin embargo, Oded Goldreich , Silvio Micali y Avi Wigderson demostraron el alcance de su poder . [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 tanto, poco práctico. Goldwasser et al. superó esto en sus "Pruebas interactivas de múltiples probadores: cómo eliminar los supuestos de intratabilidad" de 1988, 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 miente 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 idioma si hay otro probador que puede. vuelva a verificar con.
De hecho, esto es tan útil que Babai, Fortnow y Lund pudieron demostrar que MIP = NEXPTIME , la clase de todos los problemas solucionables 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 idiomas. 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 útil propiedad de que las pruebas de conocimiento cero para cada idioma en NP se pueden describir sin asumir funciones unidireccionales que debe realizar IP . Esto influye en 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 probador, puede reconocer todos los idiomas en NEXPTIME en un número constante de rondas, mostrando nuevamente su poder sobre IP. .
Se sabe que para cualquier constante k , un sistema MIP con k probadores y polinomialmente muchas 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 propiedad intelectual 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 Merlín (esencialmente mediante 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 muchos bits aleatorios polinómicamente es co- RP . El primer resultado importante de Arora y Safra fue que PCP(log, log) = NP ; Dicho de otra manera, si el verificador en el protocolo NP está obligado a elegir solo bits del certificado de prueba para examinar, esto no hará ninguna diferencia siempre que tenga bits aleatorios para usar. [15]
Además, el teorema PCP afirma que el número de accesos a la prueba se puede reducir a una constante. Eso es, . [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 . Estos problemas se estudian ahora en el campo conocido como dureza de aproximación .
![{\displaystyle \Pr[(\perp ,({\text{aceptar}}))\gets ({\tilde {\mathcal {P}}})(y)\leftrightarrow ({\mathcal {V}})( y)]<\epsilon .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89775f36bd79764d20bcbb10051edc1470cf8baa)
