IP (complejidad)

En informática teórica , y en particular en teoría de la complejidad , la clase IP (abreviatura de tiempo polinómico interactivo , es decir "interactivo en tiempo polinomial") es la clase de problemas de decisión que pueden resolverse mediante un sistema de prueba interactivo . El concepto de un sistema de prueba interactivo fue introducido por primera vez en 1985 por Shafi Goldwasser , Silvio Micali y Charles Rackoff .

Sistema de prueba interactivo

Un sistema de prueba interactivo se compone de dos máquinas:

• el prover , denotado por P, que presenta una proposición de prueba de que una cadena dada w pertenece a un cierto lenguaje formal . Se supone que el Prover tiene infinitas capacidades computacionales y espaciales ;
• el verificador , señaló V , que comprueba que la prueba presentada es correcta. El verificador es una máquina de Turing probabilística que opera en tiempo polinomial que tiene acceso a una cadena binaria aleatoria cuya longitud es polinomial en función de la longitud de w .

Las dos máquinas intercambian un número polinomial de mensajes, y cuando la interacción se completa, el verificador decide si w está en el idioma o no, con una probabilidad de error de como máximo 1/3 (por lo tanto, cualquier idioma de la clase BPP está en IP , ya que el verificador puede simplemente ignorar al Prover y tomar la decisión él mismo).

Definición

Un idioma está en PI si hay un verificador y un probador como para cualquier palabra y para cualquier probador  : L{\ Displaystyle L}V{\ Displaystyle V}PAG{\ Displaystyle P}w{\ Displaystyle w}Q{\ displaystyle Q}

w∈L⇒Pr[(V,PAG) aceptado w]≥2/3{\ Displaystyle w \ in L \ Rightarrow \ Pr [(V, P) {\ text {accept}} w] \ geq 2/3} (lo completo) w∉L⇒Pr[(V,Q) aceptado w]≤1/3{\ Displaystyle w \ notin L \ Rightarrow \ Pr [(V, Q) {\ text {accept}} w] \ leq 1/3} (corrección)

El protocolo Arthur-Merlin , introducido por László Babai , es similar, excepto que el número de turnos de interacción está limitado por una constante en lugar de un polinomio.

Goldwasser y col. han demostrado que los protocolos de extracción pública, que son los protocolos en los que el probador proporciona los números aleatorios utilizados por el verificador al mismo tiempo que las proposiciones de prueba, no son más poderosos que los protocolos de extracción aleatoria privados: de hecho, como máximo dos Se requieren rondas adicionales de interacción para replicar el efecto de un sorteo privado y, a la inversa, el verificador aún puede enviar los resultados de su sorteo privado al Prover. Esto muestra que los dos tipos de protocolos son equivalentes.

Igualdad con PSPACE

La clase de IP es igual a PSPACE . Este resultado se debe a Shamir, basado en el trabajo de Lund, Fortnow, Farloff, Nisan.

Este es un importante teorema de complejidad algorítmica, que demuestra que se puede usar un sistema de prueba interactivo para decidir si una cadena es parte de un lenguaje de tiempo polinomial, aunque la prueba tradicional en PSPACE puede ser exponencialmente larga.

Variantes

Hay una serie de variaciones de IP que alteran ligeramente la definición del sistema de evidencia interactivo. Resumimos aquí los más famosos.

aderezo

Una subclase de IP es la de las pruebas interactivas deterministas, que es similar a IP pero utiliza un verificador determinista (es decir, no aleatorio). Esta clase NP .

Completitud perfecta

Una definición equivalente de IP reemplaza la condición de que la interacción tenga éxito con una alta probabilidad en cadenas de lenguaje por la condición de que siempre tenga éxito  :

w∈L⇒Pr[V↔PAG acepta w]=1{\ Displaystyle w \ in L \ Rightarrow \ Pr [V \ leftrightarrow P {\ text {accept}} w] = 1}

Este criterio aparentemente más fuerte de "completitud perfecta" en realidad no cambia la clase de IP , ya que cualquier lenguaje con un sistema de prueba interactivo tiene un sistema de prueba interactivo con completitud perfecta.

MIP

En 1988, Goldwasser et al. han creado un sistema de prueba interactivo basado en IP aún más poderoso llamado MIP , para el cual hay dos probadores independientes. 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 más fácil detectar a un Probador malicioso tratando de engañar al verificador si hay otro Probador que pueda confirmarlo. De hecho, es tan útil que Babai, Fortnow y Lund pudieron demostrar que MIP = NEXPTIME , la clase de problemas no deterministas que se pueden resolver por máquina en tiempo exponencial , una clase muy grande. Además, todos los idiomas en NP tienen pruebas inconscientes en un sistema MIP , incluso sin suposiciones adicionales; este es un resultado conocido para IP solo asumiendo la existencia de funciones unidireccionales.

IPP

IPP ( IP ilimitada ) es una variante de IP donde el verificador BPP es reemplazado por un verificador PP . Más precisamente, se modifican las condiciones de completitud y corrección de la siguiente manera:

• Integridad  : si una cadena está en el idioma, el verificador honesto estará convencido de ello con una probabilidad de al menos 1/2;
• Corrección : si la cadena no está en el idioma, ningún probador podrá convencer al verificador honesto de que está con una probabilidad mayor a 1/2.

Aunque IPP es igual a PSPACE , los protocolos IPP se comportan de manera bastante diferente a los de IP hacia los oráculos  : IPP = PSPACE hacia todos los oráculos, mientras que IP ≠ PSPACE para algunos oráculos oráculos.

QIP

QIP es una versión de IP donde el verificador BPP es reemplazado por un verificador BQP , donde BQP es la clase de problemas decidibles por computadoras cuánticas en tiempo polinomial. Los mensajes se componen de qubits.

Kitaev y Watrous muestran que QIP está incluido en EXPTIME . En 2009, Jain, Ji, Upadhyay y Watrous demostraron que QIP de hecho también es igual a PSPACE , lo que implica que esto no agrega potencia al protocolo.

compIP

Mientras que IPPP y QIP dan más poder al verificador, un sistema compIP ( Competitive IP Evidence System ) debilita la condición de integridad de una manera que debilita al Prover:

• Integridad : si la cadena está en el idioma L , el verificador honesto será convencido de esto por un probador honesto con una probabilidad de al menos 2/3. Por otra parte, el Demostrador debe hacerlo probabilitistically en tiempo polinómico por tener un oráculo en el L idioma .

Básicamente, esto convierte al Prover en una máquina BPP con un oráculo en el lenguaje, pero solo en el caso de que esté completo, no en el caso de corrección. La idea es que si un idioma está en compIP , probarlo de forma interactiva es tan fácil como decidir. Con el oráculo, el Prover puede resolver fácilmente el problema, pero su poder limitado hace que sea mucho más difícil convencer al verificador de cualquier cosa. De hecho, ni siquiera se conoce ni se considera que compIP contenga NP .

Sin embargo, dicho sistema puede resolver algunos problemas que se consideran difíciles. Paradójicamente, incluso si uno no piensa que tal sistema es capaz de resolver todos los NP , puede resolver fácilmente todos los problemas NP-completos gracias a su autorreductibilidad. Esto se debe al hecho de que si el lenguaje L no es NP -difficile, el Prover está fuertemente limitado en su poder (ya que ya no puede decidir todos los problemas NP con su oráculo).

Además, el problema del nonisomorfismo gráfico (que es un problema clásico en IP ) también está en compIP , ya que la única operación difícil con la que el Prover puede estar satisfecho es la prueba de isomorfismo, para la cual puede usar un oráculo. Los problemas de residualidad cuadrática e isomorfismo gráfico también están en compIP . Tenga en cuenta que la no residualidad cuadrática (QNR) es probablemente un problema más simple que el isomorfismo gráfico, ya que QNR está en UP intersect co-UP .

Notas y referencias

• (fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado "  IP (complejidad)  " ( consulte la lista de autores ) .

1. Goldwasser, Micali y Rackoff 1985 .
2. Goldwasser, Micali y Rackoff 1989 .
3. Babai, 1985 .
4. Adi Shamir , “  IP = PSPACE  ”, J. ACM , vol.  39, n o  4,Octubre de 1992, p.  869–877 ( ISSN  0004-5411 , DOI  10.1145 / 146585.146609 , leído en línea , consultado el 11 de julio de 2019 )
5. Carsten Lund , Lance Fortnow , Howard Karloff y Noam Nisan , "  Métodos algebraicos para sistemas de prueba interactivos  ", J. ACM , vol.  39, n o  4,Octubre de 1992, p.  859–868 ( ISSN  0004-5411 , DOI  10.1145 / 146585.146605 , leído en línea , consultado el 11 de julio de 2019 )
6. Martin Furer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos. Sobre la integridad y solidez de los sistemas de prueba interactivos . Advances in Computing Research: An Research Annual , 5: 429-442. 1989.
7. R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan y P. Rohatgi. La hipótesis del oráculo aleatorio es falsa . Revista de Ciencias de la Computación y Sistemas , 49 (1): 24-39. 1994.
8. J. Watrous. PSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante . Actas de IEEE FOCS'99 , págs. 112-119. 1999.
9. A. Kitaev y J. Watrous. “  Paralelización, amplificación y simulación de tiempo exponencial de sistemas de prueba interactivos cuánticos  ” ( Archivo • Wikiwix • Archive.is • Google • ¿Qué hacer? ) . Actas de ACM STOC'2000 , págs. 608-617. 2000.
10. (in) Autor desconocido "  QIP = PSPACE  "2009. .
11. (en) Shafi Goldwasser y Mihir Bellare , "  La complejidad de la toma frente búsqueda  " [PDF] , SIAM Journal on Computing , Volumen 23, N o  1 febrero de 1994.
12. Cai JY, Threlfall RA, 2004. "Una nota sobre residuosidad cuadrática y UP ". Cartas de procesamiento de información 92 (3): 127-131.

Bibliografía

• László Babai , "Teoría de grupos comerciales para la aleatoriedad" , en Actas del decimoséptimo simposio de ACM sobre teoría de la computación (STOC) , Providence (Rhodes Island), ACM,1985( leer en línea ).
• Shafi Goldwasser , Silvio Micali y Charles Rackoff , "La complejidad del conocimiento de los sistemas de prueba interactivos" , en Proceedings of Seventeenth ACM Symposium on the Theory of Computation (STOC) , Providence (Rhodes Island), ACM,1985( leer en línea ) , pág.  291-304. Resumen detallado .
• Shafi Goldwasser , Silvio Micali y Charles Rackoff , "  La complejidad del conocimiento de los sistemas de prueba interactivos  ", SIAM Journal on Computing , Filadelfia, Sociedad de Matemáticas Industriales y Aplicadas , vol.  18, n o  1,1989, p.  186–208 ( ISSN  1095-7111 , DOI  10.1137 / 0218012 , leer en línea )

enlaces externos

• (es) La clase de IP en Complexity Zoo
• ( fr ) La clase MIP en el Complexity Zoo
• ( fr ) Clase IIP en el Complexity Zoo
• ( fr ) La clase QIP en el Complexity Zoo

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">