En la teoría de la complejidad computacional , la clase IP (que significa tiempo polinomial interactivo) es la clase de problemas que se pueden resolver mediante un sistema de prueba interactivo . Es igual a la clase PSPACE . El resultado se estableció en una serie de artículos: el primero de Lund, Karloff, Fortnow y Nisan mostró que co-NP tenía múltiples pruebas interactivas de probadores; [1] y el segundo, de Shamir, emplearon su técnica para establecer que IP = PSPACE. [2] El resultado es un ejemplo famoso en el que la prueba no se relativiza . [3]
El concepto de un sistema de prueba interactivo fue introducido por primera vez por Shafi Goldwasser , Silvio Micali y Charles Rackoff en 1985. Un sistema de prueba interactivo consta de dos máquinas, un prover, P , que presenta una prueba de que una cadena dada n es miembro de algún lenguaje , y un verificador, V , que verifica que la prueba presentada sea correcta. Se supone que el comprobador es infinito en cálculo y almacenamiento, mientras que el verificador es una máquina probabilística de tiempo polinomial con acceso a una cadena de bits aleatoria cuya longitud es polinomial del tamaño de n . Estas dos máquinas intercambian un número polinomial, p (n ), de mensajes y una vez completada la interacción, el verificador debe decidir si n está en el idioma o no , con solo 1/3 de probabilidad de error. (Entonces, cualquier idioma en BPP está en IP , ya que entonces el verificador podría simplemente ignorar al prover y tomar la decisión por sí mismo).
Definición
Una lengua L pertenece a IP si existe V , P tal que para todo Q , w :
El protocolo Arthur-Merlin , introducido por László Babai , es de naturaleza similar, excepto que el número de rondas de interacción está limitado por una constante en lugar de un polinomio.
Goldwasser y col. han demostrado que los protocolos de monedas públicas , donde los números aleatorios utilizados por el verificador se proporcionan al probador junto con los desafíos, no son menos poderosos que los protocolos de monedas privadas. Se requieren como máximo dos rondas adicionales de interacción para replicar el efecto de un protocolo de moneda privada. La inclusión opuesta es sencilla, porque el verificador siempre puede enviar al probador los resultados de sus lanzamientos privados de monedas, lo que demuestra que los dos tipos de protocolos son equivalentes.
En la siguiente sección probamos que IP = PSPACE , un teorema importante en complejidad computacional, que demuestra que un sistema de prueba interactivo puede usarse para decidir si una cadena es miembro de un lenguaje en tiempo polinomial, aunque la prueba tradicional de PSPACE puede ser exponencialmente largo.
Prueba de IP = PSPACE
La prueba se puede dividir en dos partes, mostramos que IP ⊆ PSPACE y PSPACE ⊆ IP .
IP ⊆ PSPACE
Para demostrar que IP ⊆ PSPACE , presentamos una simulación de un sistema de prueba interactivo mediante una máquina espacial polinomial. Ahora, podemos definir:
y para cada 0 ≤ j ≤ py cada historial de mensajes M j , definimos inductivamente la función N M j :
dónde:
donde Pr r es la probabilidad asumida sobre la cadena aleatoria r de longitud p . Esta expresión es el promedio de N M j + 1 , ponderado por la probabilidad de que el verificador haya enviado el mensaje m j + 1 .
Tome M 0 como la secuencia de mensajes vacía, aquí mostraremos que N M 0 se puede calcular en un espacio polinomial, y que N M 0 = Pr [ V acepta w ]. Primero, para calcular N M 0 , un algoritmo puede calcular recursivamente los valores N M j para cada j y M j . Dado que la profundidad de la recursividad es p , solo es necesario el espacio polinomial. El segundo requisito es que necesitamos N M 0 = Pr [ V acepta w ], el valor necesario para determinar si w está en A. Usamos la inducción para demostrar esto de la siguiente manera.
Debemos demostrar que para cada 0 ≤ j ≤ py cada M j , N M j = Pr [ V acepta w comenzando en M j ], y lo haremos usando inducción en j . El caso base es probar para j = p . Luego usaremos la inducción para bajar de p a 0.
El caso base de j = p es bastante simple. Dado que m p es aceptar o rechazar, si m p es aceptar, N M p se define como 1 y Pr [ V acepta w comenzando en M j ] = 1 ya que el flujo de mensajes indica aceptación, por lo que la afirmación es verdadera. Si m p es rechazar, el argumento es muy similar.
Para la hipótesis inductiva, asumimos que para algún j +1 ≤ py cualquier secuencia de mensajes M j + 1 , N M j + 1 = Pr [ V acepta w comenzando en M j + 1 ] y luego probamos la hipótesis para j y cualquier secuencia de mensajes M j .
Si j es par, m j + 1 es un mensaje de V a P . Según la definición de N M j ,
Entonces, por la hipótesis inductiva, podemos decir que esto es igual a
Finalmente, por definición, podemos ver que esto es igual a Pr [ V acepta w comenzando en M j ].
Si j es impar, m j + 1 es un mensaje de P a V . Por definición,
Entonces, por la hipótesis inductiva, esto es igual a
Esto es igual a Pr [ V acepta w comenzando en M j ] ya que:
porque el probador del lado derecho podría enviar el mensaje m j + 1 para maximizar la expresión del lado izquierdo. Y:
Dado que el mismo Prover no puede hacer nada mejor que enviar el mismo mensaje. Por lo tanto, esto es válido tanto si i es par como si es impar y la prueba de que IP ⊆ PSPACE es completa.
Aquí hemos construido una máquina del espacio polinomio que utiliza la mejor cámara de fermentación P para una determinada cadena w en el lenguaje A . Usamos este mejor probador en lugar de un probador con bits de entrada aleatorios porque podemos probar cada conjunto de bits de entrada aleatorios en el espacio polinomial. Dado que hemos simulado un sistema de prueba interactivo con una máquina espacial polinomial, hemos demostrado que IP ⊆ PSPACE , como se desea.
PSPACE ⊆ IP
Para ilustrar la técnica que se utilizará para probar PSPACE ⊆ IP , primero probaremos un teorema más débil, que fue probado por Lund, et al .: #SAT ∈ IP . Luego, usando los conceptos de esta demostración, la ampliaremos para mostrar que TQBF ∈ IP . Desde TQBF ∈ PSPACE -completo, y TQBF ∈ IP luego PSPACE ⊆ IP .
#SAT es miembro de IP
Comenzamos mostrando que #SAT está en IP , donde:
Tenga en cuenta que esto es diferente de la definición normal de #SAT , en que es un problema de decisión, más que una función.
Primero usamos la aritmetización para mapear la fórmula booleana con n variables, φ ( b 1 , ..., b n ) a un polinomio p φ ( x 1 , ..., x n ), donde p φ imita φ en ese p φ es 1 si φ es verdadero y 0 en caso contrario, siempre que a las variables de p φ se les asignen valores booleanos. Las operaciones booleanas ∨, ∧ y ¬ utilizadas en φ se simulan en p φ reemplazando los operadores en φ como se muestra en la siguiente tabla.
a ∧ b | ab |
a ∨ b | a ∗ b : = 1 - (1 - a ) (1 - b ) |
¬ a | 1 - a |
Como ejemplo, φ = a ∧ b ∨ ¬ c se convertiría en un polinomio de la siguiente manera:
Las operaciones de ab y un * b cada resultado en un polinomio con un grado limitado por la suma de los grados de los polinomios para una y b y por lo tanto, el grado de cualquier variable es en la mayoría de la longitud de φ.
Ahora sea F un campo finito de orden q > 2 n ; también exija que q sea al menos 1000. Para cada 0 ≤ i ≤ n , defina una función f i en F , que tenga parámetros, y una sola variable a i en F : Para 0 ≤ i ≤ n y para dejar
Tenga en cuenta que el valor de f 0 es el número de asignaciones satisfactorias de φ. f 0 es una función nula, sin variables.
Ahora el protocolo para #SAT funciona de la siguiente manera:
- Fase 0 : La cámara de fermentación P elige un primer q > 2 n y calcula f , que envía entonces q y f 0 al verificador V . V comprueba que q es un primo mayor que max (1000, 2 n ) y que f 0 () = k .
- Fase 1 : P envía los coeficientes de f 1 ( z ) como un polinomio en z. V verifica que el grado de f 1 sea menor que ny que f 0 = f 1 (0) + f 1 (1). (Si no, V rechaza). V ahora envía un número aleatorio r 1 de F a P .
- Fase i : P envía los coeficientes decomo polinomio en z . V verifica que el grado de f i es menor que ny que. (Si no, V rechaza). V ahora envía un número aleatorio r i de F a P .
- Fase n + 1 : V evalúa para comparar con el valor . Si son iguales, V acepta; de lo contrario, V rechaza.
Tenga en cuenta que este es un algoritmo de moneda pública.
Si φ tiene k asignaciones satisfactorias, claramente V aceptará. Si φ no tiene k asignaciones satisfactorias asumimos que hay un probadorque intenta convencer a V de que φ tiene k asignaciones satisfactorias. Mostramos que esto solo se puede hacer con baja probabilidad.
Para evitar que V rechace en la fase 0, tiene que enviar un valor incorrecto a P . Luego, en la fase 1, debe enviar un polinomio incorrecto con la propiedad que . Cuando V elige un r 1 aleatorio para enviar a P ,
Esto se debe a que un polinomio en una sola variable de grado d como máximo no puede tener más de d raíces (a menos que siempre se evalúe como 0). Entonces, dos polinomios cualesquiera en una sola variable de grado como máximo d pueden ser iguales solo en d lugares. Desde | F | > 2 n las posibilidades de que r 1 sea uno de estos valores es como máximosi n > 10, o como máximo ( n / 1000) ≤ ( n / n 3 ) si n ≤ 10.
Generalizando esta idea para las otras fases tenemos para cada 1 ≤ i ≤ n si
entonces para r i elegido al azar de F ,
Hay n fases, por lo que la probabilidad de quetiene suerte porque V selecciona en algún momento un r i conveniente como máximo 1 / n . Por tanto, ningún probador puede hacer que el verificador acepte con una probabilidad superior a 1 / n . También podemos ver en la definición que el verificador V opera en tiempo polinomial probabilístico. Así, #SAT ∈ IP .
TQBF es miembro de IP
Para mostrar que PSPACE es un subconjunto de IP , debemos elegir un problema completo de PSPACE y demostrar que está en IP . Una vez que mostramos esto, queda claro que PSPACE ⊆ IP . La técnica de prueba demostrada aquí se le atribuye a Adi Shamir .
Sabemos que TQBF está en PSPACE-Complete . Entonces, sea ψ una expresión booleana cuantificada:
donde φ es una fórmula CNF. Entonces Q i es un cuantificador, ya sea ∃ o ∀. Ahora f i es el mismo que en la demostración anterior, pero ahora también incluye cuantificadores.
Aquí, φ ( a 1 , ..., a i ) es φ con un 1 a a i sustituido por x 1 a x i . Por tanto, f 0 es el valor de verdad de ψ. Para aritmetizar ψ debemos usar las siguientes reglas:
donde, como antes, definimos x ∗ y = 1 - (1 - x ) (1 - y ).
Al usar el método descrito en #SAT, debemos enfrentar el problema de que para cualquier f i el grado del polinomio resultante puede duplicarse con cada cuantificador. Para evitar esto, debemos introducir un nuevo operador de reducción R que reducirá los grados del polinomio sin cambiar su comportamiento en las entradas booleanas.
Así que ahora, antes de aritmetizar introducimos una nueva expresión:
o dicho de otra manera:
Ahora para cada i ≤ k definimos la función f i . También definimosser el polinomio p ( x 1 , ..., x m ) que se obtiene aritmetizando φ. Ahora, para mantener bajo el grado del polinomio, definimos f i en términos de f i + 1 :
Ahora podemos ver que la operación de reducción R, no cambia el grado del polinomio. También es importante ver que la operación R x no cambia el valor de la función en entradas booleanas. Entonces f 0 sigue siendo el valor de verdad de ψ, pero el valor de R x produce un resultado que es lineal en x . También después de cualquier añadimos en ψ ′ para reducir el grado a 1 después de aritmetizar .
Ahora describamos el protocolo. Si n es la longitud de ψ, todas las operaciones aritméticas en el protocolo están sobre un campo de tamaño al menos n 4 donde n es la longitud de ψ.
- Fase 0 : P → V : P envía f 0 a V . V comprueba que f 0 = 1 y rechaza si no.
- Fase 1 : P → V : P envía f 1 ( z ) a V . V usa coeficientes para evaluar f 1 (0) yf 1 (1). Luego verifica que el grado del polinomio sea como máximo n y que las siguientes identidades sean verdaderas:
- Si alguno falla, rechace.
- Fase i : P → V : P envíacomo polinomio en z . r 1 denota los valores aleatorios establecidos previamente para
V usa coeficientes para evaluar y . Luego verifica que el grado del polinomio sea como máximo n y que las siguientes identidades sean verdaderas:
Si alguno falla, rechace.
V → P : V elige una r aleatoria en F y la envía a P. (Sientonces esta r reemplaza a la anterior r ).
Ir a la fase i + 1 donde P debe persuadir a V de que es correcto.
- Fase k + 1 : V evalúa. Luego comprueba siSi son iguales, V acepta; de lo contrario, V rechaza.
Este es el final de la descripción del protocolo.
Si ψ es verdadero, V aceptará cuando P siga el protocolo. Del mismo modo si es un probador malicioso que miente, y si ψ es falso, entonces tendrá que estar en la fase 0 y enviar algún valor para f 0 . Si en la fase i , V tiene un valor incorrecto para luego y probablemente también sea incorrecta, etc. La probabilidad depara tener suerte en algún r aleatorio es como máximo el grado del polinomio dividido por el tamaño del campo:. El protocolo pasa por fases O ( n 2 ), por lo que la probabilidad de quetiene suerte en alguna fase es ≤ 1 / n . Sinunca tiene suerte, entonces V rechazará en la fase k +1.
Dado que ahora hemos demostrado que tanto IP ⊆ PSPACE como PSPACE ⊆ IP , podemos concluir que IP = PSPACE como se desea. Además, hemos demostrado que cualquier algoritmo de IP puede tomarse como moneda pública, ya que la reducción de PSPACE a IP tiene esta propiedad.
Variantes
Hay una serie de variantes de IP que modifican ligeramente la definición del sistema de prueba interactivo. Resumimos algunos de los más conocidos aquí.
aderezo
Un subconjunto de la propiedad intelectual es la clase de prueba interactiva determinista , que es similar a la propiedad intelectual pero tiene un verificador determinista (es decir, sin aleatoriedad). Esta clase es igual a NP .
Completitud perfecta
Una definición equivalente de IP reemplaza la condición de que la interacción tenga éxito con alta probabilidad en cadenas en el idioma con el requisito de que siempre tenga éxito:
Este criterio aparentemente más fuerte de "completitud perfecta" no cambia la clase de complejidad IP , ya que cualquier lenguaje con un sistema de prueba interactivo puede recibir un sistema de prueba interactivo con una completitud perfecta. [4]
MIP
En 1988, Goldwasser et al. creó un sistema de prueba interactivo aún más poderoso basado en IP llamado MIP en el que 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 delincuente está mintiendo si él y su compañero son interrogados en habitaciones separadas, es considerablemente más fácil detectar a un probador malintencionado que intenta engañar al verificador si hay otro probador con el que pueda volver a verificar. 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. Además, todos los idiomas en NP tienen pruebas de conocimiento cero en un sistema MIP , sin suposiciones adicionales; esto solo se conoce para IP asumiendo la existencia de funciones unidireccionales.
IPP
IPP ( IP ilimitada ) es una variante de IP en la que reemplazamos el verificador BPP por un verificador PP . Más precisamente, modificamos las condiciones de integridad y solidez de la siguiente manera:
- Integridad : si una cadena está en el idioma, el verificador honesto será convencido de este hecho por un probador honesto con probabilidad de al menos 1/2.
- Solidez : si la cuerda no está en el idioma, ningún probador puede convencer al verificador honesto de que está en el idioma, excepto con una probabilidad menor a 1/2.
Aunque IPP también es igual a PSPACE , los protocolos IPP se comportan de manera bastante diferente a IP con respecto a los oráculos : IPP = PSPACE con respecto a todos los oráculos, mientras que IP ≠ PSPACE con respecto a casi todos los oráculos. [5]
QIP
QIP es una versión de IP que reemplaza elverificador BPP por unverificador BQP , donde BQP es la clase de problemas que pueden resolver las computadoras cuánticas en tiempo polinomial. Los mensajes se componen de qubits. [6] En 2009, Jain, Ji, Upadhyay y Watrous demostraron que QIP también es igual a PSPACE , [7] lo que implica que este cambio no otorga poder adicional al protocolo. Esto subsume un resultado anterior de Kitaev y Watrous de que QIP está contenido en EXPTIME porque QIP = QIP [3], por lo que nunca son necesarias más de tres rondas. [8]
compIP
Mientras que IPP y QIP dan más poder al verificador, un sistema compIP (sistema competitivo a prueba de IP ) debilita la condición de integridad de una manera que debilita al prover:
- Integridad : si una cadena está en la lengua L , el verificador honesto será convencido de este hecho por un probador honesto con probabilidad de al menos 2/3. Por otra parte, la cámara de fermentación lo hará en el tiempo de acceso probabilístico polinomio dado a un oráculo para el lenguaje L .
Esencialmente, esto convierte al prover en una máquina BPP con acceso a un oráculo para el lenguaje, pero solo en el caso de integridad, no en el caso de solidez. El concepto es que si un idioma está en compIP , demostrarlo de forma interactiva es, en cierto sentido, tan fácil como decidirlo. Con el oráculo, el probador 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 sabe ni se cree que compIP contenga NP .
Por otro lado, dicho sistema puede resolver algunos problemas que se creen difíciles. De manera algo paradójica, aunque no se cree que un sistema de este tipo sea capaz de resolver todo el NP , puede resolver fácilmente todos los problemas NP-completos debido a la autorreductibilidad. Esto se debe al hecho de que si el lenguaje L no es NP- duro, el prover tiene un poder sustancialmente limitado (ya que ya no puede decidir todos los problemas NP con su oráculo).
Además, el problema del no isomorfismo gráfico (que es un problema clásico en IP ) también está en compIP , ya que la única operación difícil que tiene que hacer el probador es la prueba de isomorfismo, que puede usar el oráculo para resolver. La no-residuosidad cuadrática y el isomorfismo gráfico también están en compIP . [9] Tenga en cuenta que la no-residuosidad cuadrática (QNR) es probablemente un problema más fácil que el isomorfismo gráfico, ya que QNR está en UP intersect co-UP . [10]
Notas
- ^ Lund, C .; Fortnow, L .; Karloff, H .; Nisan, N. (1990). "Métodos algebraicos para sistemas de prueba interactivos". Proceedings [1990] 31º Simposio Anual sobre Fundamentos de las Ciencias de la Computación . Computación IEEE. Soc. Presione: 2–10. doi : 10.1109 / fscs.1990.89518 . ISBN 0-8186-2082-X.
- ^ Shamir, Adi. "Ip = pspace". Journal of the ACM 39.4 (1992): 869-877.
- ^ Chang Richard; et al. (1994). "La hipótesis del oráculo aleatorio es falsa". Revista de Ciencias de la Computación y Sistemas . 49 (1): 24–39. doi : 10.1016 / s0022-0000 (05) 80084-4 .
- ^ Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis (1989). "Sobre integridad y solidez en sistemas de prueba interactivos". Avances en la investigación de la computación: una investigación anual . 5 : 429–442. CiteSeerX 10.1.1.39.9412 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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.
- ^ J. Watrous. PSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante . Actas de IEEE FOCS'99 , págs. 112-119. 1999.
- ^ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (2009). "QIP = PSPACE". arXiv : 0907,4737 [ quant-ph ].
- ^ A. Kitaev y J. Watrous. Paralelización, amplificación y simulación de tiempo exponencial de sistemas de prueba interactivos cuánticos . Actas del 32º Simposio ACM sobre Teoría de la Computación , págs. 608-617. 2000.
- ^ Shafi Goldwasser y Mihir Bellare . La complejidad de la decisión frente a la búsqueda . SIAM Journal on Computing , Volumen 23, No. 1. Febrero de 1994.
- ^ Cai JY, Threlfall RA (2004). "Una nota sobre residuosidad cuadrática y UP ". Cartas de procesamiento de información . 92 (3): 127-131. CiteSeerX 10.1.1.409.1830 . doi : 10.1016 / j.ipl.2004.06.015 .
Referencias
- Babai, L. Teoría de grupos comerciales para la aleatoriedad. En Actas del 17º Simposio ACM sobre Teoría de la Computación. ACM, Nueva York, 1985, págs. 421–429.
- Shafi Goldwasser , Silvio Micali y Charles Rackoff . La complejidad del conocimiento de los sistemas de prueba interactivos . Actas del 17º Simposio de ACM sobre teoría de la computación , Providence, Rhode Island. 1985, págs. 291-304. Abstracto extendido
- Shafi Goldwasser y Michael Sipser. Monedas privadas versus monedas públicas en sistemas de prueba interactivos . Actas del 18º Simposio Anual ACM sobre Teoría de la Computación . ACM, Nueva York, 1986, págs. 59–68.
- Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [1]
- Lund, C. , Fortnow, L. , Karloff, H., Nisan, N. Métodos algebraicos para sistemas de prueba interactivos. En Actas del 31º Simposio sobre los fundamentos de la informática. IEEE, Nueva York, 1990, págs. 2-90.
- Adi Shamir. IP = PSPACE . Journal of the ACM , volumen 39, número 4, p. 869–877. Octubre de 1992.
- Alexander Shen. IP = PSpace: Prueba simplificada . J.ACM, v. 39 (4), págs. 878–880, 1992.
- Zoológico de complejidad : IP , MIP , IPP , QIP , QIP (2) , compIP , frIP