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 determinada cadena 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ómputo 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 correcto.
Todos los sistemas de prueba interactivos tienen dos requisitos:
- Exhaustividad : si la afirmación es verdadera, el verificador honesto (es decir, uno que sigue el protocolo correctamente) puede ser convencido de este hecho por un probador que no sea de confianza.
- Solidez : si la afirmación es falsa, ningún probador, incluso si no sigue el protocolo, puede convencer al verificador honesto de que es verdadera, excepto con una pequeña probabilidad .
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 habilidades que se le dan; por ejemplo, la mayoría de los sistemas de prueba interactivos dependen críticamente de la la capacidad del verificador para tomar decisiones al azar. 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 .
notario público
La clase de complejidad NP puede verse como 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 mira la entrada y calcula la solución usando su potencia ilimitada y devuelve un certificado de prueba de tamaño polinomial.
- El verificador verifica que el certificado sea válido en tiempo polinomial determinista. Si es válido, acepta; de lo contrario, lo rechaza.
En el caso de que exista un certificado de prueba válido, el probador siempre puede hacer que el verificador acepte dá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 comprobador, por malicioso que sea, puede convencer al verificador de lo contrario, porque cualquier certificado de prueba será rechazado.
Protocolos Arthur-Merlin y Merlin-Arthur
Aunque se puede considerar que 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ó "Teoría de grupos comerciales para la aleatoriedad", [1] 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 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 requerir que el verificador siempre acepte certificados válidos y rechace certificados inválidos, es más indulgente:
- Integridad: si la cadena está en el idioma, el probador debe poder dar un certificado tal que el verificador acepte con probabilidad al menos 2/3 (dependiendo de las elecciones aleatorias del verificador).
- Solidez: si la cadena no está en el idioma, ningún probador, por 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 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 cálculos prácticos abstractos (ver BPP ).
Protocolo de monedas públicas versus protocolo de monedas privadas
En un protocolo de monedas públicas , las elecciones aleatorias realizadas por el verificador se hacen públicas. Permanecen privados en un protocolo de monedas privado.
En la misma conferencia donde Babai definió su sistema de prueba para MA , Shafi Goldwasser , Silvio Micali y Charles Rackoff [2] 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 el cálculo y pasa un mensaje al probador, y el probador realiza el cálculo y devuelve la 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 verificador y P es un turno de comprobador.
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 prover todos los bits aleatorios que usa en su cálculo. El resultado es que el verificador no puede "ocultar" nada del 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 denomina protocolo público de monedas , porque los bits aleatorios ("lanzamientos de monedas") son visibles para ambas máquinas. Por el contrario, el enfoque de IP se denomina protocolo de monedas privado .
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 de las principales motivaciones a la hora de definir los sistemas a prueba de propiedad intelectual .
En 1986, Goldwasser y Sipser [3] demostraron, quizás sorprendentemente, que la capacidad del verificador para ocultar los lanzamientos de monedas al probador no sirve de mucho después de todo, ya que un protocolo público de monedas Arthur-Merlin con solo dos rondas más puede reconocer todas las mismos idiomas. El resultado es que los protocolos de monedas públicas y monedas privadas son aproximadamente equivalentes. De hecho, como muestra Babai en 1988, AM [ k ] = AM para todas las k constantes , por lo que el IP [ k ] no tiene ventaja sobre AM . [4]
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 para 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 las gráficas sean iguales. Resulta que el complemento del problema de isomorfismo gráfico, un problema de 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. [5]
IP
Las monedas privadas pueden no ser útiles, pero más rondas de interacción son útiles. Si permitimos que la máquina verificadora probabilística y el probador todopoderoso interactúen durante un número polinomio de rondas, obtenemos la clase de problemas denominada 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 puede resolver una máquina de Turing determinista ordinaria en el espacio polinomial. [6]
QIP
Si permitimos que los elementos del sistema utilicen la computación cuántica , el sistema se denomina sistema de prueba interactivo cuántico y la clase de complejidad correspondiente se denomina QIP . [7] Una serie de resultados culminó en un gran avance en 2010 que QIP = PSPACE . [8] [9]
Conocimiento cero
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 al verificador. 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 el verificador no ha visto un certificado, pero 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 PI de Goldwasser, Micali y Rackoff, pero Oded Goldreich , Silvio Micali y Avi Wigderson demostraron el alcance de su poder . [5]
MIP
Uno de los objetivos de los diseñadores de IP era crear el sistema de prueba interactivo más poderoso posible, y al principio parece que no se puede hacer más poderoso sin hacer que el verificador sea más poderoso y tan poco práctico. Goldwasser y col. superó esto en su 1988 "Pruebas interactivas de múltiples probadores: Cómo eliminar los supuestos de intratabilidad", que define una variante de IP llamada MIP en la que hay dos probadores independientes. [10] 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 delincuente está mintiendo si él y su pareja 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 pueda. verifique dos veces con.
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. [11] 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 de 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 pueden describirse sin la suposición de funciones unidireccionales que debe realizar IP . Esto influye en el diseño de algoritmos criptográficos demostrablemente irrompibles. [10] 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 comprobador, 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. [12]
PCP
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 Merlín (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 muchos bits aleatorios polinomiales 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 sólo partes del certificado de prueba para mirar, esto no hará ninguna diferencia siempre que tenga bits aleatorios para usar. [13]
Además, el teorema de PCP afirma que el número de accesos de prueba puede reducirse hasta una constante. Es decir,. [14] Utilizaron esta valiosa caracterización de NP para demostrar que los algoritmos de aproximación no existen 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 .
Ver también
- Máquina de Oracle
Referencias
- ^ László Babai. Teoría de grupos de intercambio por aleatoriedad . Actas del Decimoséptimo Simposio Anual sobre Teoría de la Computación , ACM. 1985.
- ^ Goldwasser, S .; Micali, S .; Rackoff, C. (1989). "La complejidad del conocimiento de los sistemas de prueba interactivos" (PDF) . Revista SIAM de Computación . 18 (1): 186–208. doi : 10.1137 / 0218012 . ISSN 1095-7111 . Abstracto extendido
- ^ Shafi Goldwasser y Michael Sipser. Monedas privadas versus monedas públicas en sistemas de prueba interactivos . Actas de ACM STOC'86 , págs. 58–68. 1986.
- ^ László Babai y Shlomo Moran . Juegos de Arthur-Merlin: un sistema de prueba aleatorio y una jerarquía de clases de complejidad . Revista de Ciencias de la Computación y Sistemas , 36: p.254–276. 1988.
- ↑ a b O. Goldreich, S. Micali, A. Wigderson. Pruebas que no aportan nada más que su validez . Journal of the ACM , volumen 38, número 3, p.690–728. Julio de 1991.
- ^ Adi Shamir. IP = PSPACE . Journal of the ACM , volumen 39, número 4, págs. 869–877. Octubre de 1992.
- ^ Tsuyoshi Ito; Hirotada Kobayashi; John Watrous (2010). "Pruebas interactivas cuánticas con límites de error débiles". arXiv : 1012,4427v2 [ quant-ph ].
- ^ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2010). "QIP = PSPACE". STOC '10: Actas del 42º simposio ACM sobre teoría de la computación . ACM. págs. 573–582. ISBN 978-1-4503-0050-6.
- ^ Aaronson, S. (2010). "Avance QIP = PSPACE". Comunicaciones de la ACM . 53 (12): 101. doi : 10.1145 / 1859204.1859230 .
- ^ a b M. Ben-or, Shafi Goldwasser, J. Kilian y A. Wigderson. Pruebas interactivas de múltiples probadores: cómo eliminar suposiciones de intratabilidad . Actas del 20º Simposio ACM sobre Teoría de la Computación , págs. 113–121. 1988.
- ^ László Babai, L. Fortnow y C. Lund. El tiempo exponencial no determinista tiene protocolos interactivos de dos probadores . Complejidad computacional , volumen 1, págs. 3-40. 1991.
- ^ http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf
- ^ Sanjeev Arora y Shmuel Safra . Comprobación probabilística de pruebas: una nueva caracterización de NP . Journal of the ACM , volumen 45, número 1, págs. 70-122. Enero de 1998.
- ^ Sanjeev Arora, C. Lund, R. Motwani, M. Sudan y M. Szegedy. Verificación de pruebas y problemas de dureza de aproximación . Actas del 33º Simposio del IEEE sobre fundamentos de la informática, págs. 13–22. 1992.
Libros de texto
- Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach" , Cambridge University Press, marzo de 2009.
- Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 978-0-534-94728-6. Sección 10.4: Sistemas de prueba interactivos, págs. 354–366.
- Christos Papadimitriou (1993). Complejidad computacional (1ª ed.). Addison Wesley. ISBN 978-0-201-53082-7. Sección 19.2: Juegos contra la naturaleza y protocolos interactivos, págs. 469–480.
enlaces externos
- Dexter Kozen. Pruebas interactivas . CS682 Notas de la conferencia de primavera de 2004. Departamento de Ciencias de la Computación, Universidad de Cornell.
- Zoológico de complejidad :
- MA , MA ' , MAEXP , MAE
- AM , AMEXP , AM intersectan co-AM , AM [polylog] , coAM , BP • NP
- QMA , QMA + , QMA (2) , QMA registro , QMAM
- IP , MIP , IPP , QIP , QIP (2) , compIP , frIP
- PCP (r (n), q (n))
- Larry Gonick. "¿ Prueba positiva? ". Una tira cómica sobre sistemas de prueba interactivos.