IP (complejidad)

En la teoría de la complejidad computacional , la clase IP (que significa Interactive Proof ) es la clase de problemas que se pueden resolver mediante un sistema de pruebas interactivas . 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 el co-NP tenía múltiples pruebas interactivas con probadores; ^[1] y el segundo, de Shamir, empleó su técnica para establecer que IP=PSPACE. ^[2] El resultado es un ejemplo famoso en el que la prueba no 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 probador, 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 probador es infinito en computación y almacenamiento, mientras que el verificador es una máquina de tiempo polinomial probabilística con acceso a una cadena de bits aleatoria cuya longitud es polinomial en el tamaño de n . Estas dos máquinas intercambian un número polinomial, p ( n ), de mensajes y una vez que se completa la interacción, el verificador debe decidir si n está o no en el lenguaje, con solo una probabilidad de error de 1/3. (Por lo tanto, cualquier lenguaje en BPP está en IP , ya que entonces el verificador podría simplemente ignorar al probador y tomar la decisión por su cuenta).

Representación general de un protocolo de prueba interactivo.

Definición

Un lenguaje L pertenece a IP si existen V , P tales que para todo Q , w :

${\displaystyle w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]\geq {\tfrac {2}{3}}}$

${\displaystyle w\not \in L\Rightarrow \Pr[V\leftrightarrow Q{\text{ accepts }}w]\leq {\tfrac {1}{3}}}$

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 et al. han demostrado que los protocolos de moneda pública , en los que 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 moneda privada. 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 de moneda privados, lo que demuestra que los dos tipos de protocolos son equivalentes.

En la siguiente sección demostramos que IP = PSPACE , un teorema importante en complejidad computacional, que demuestra que se puede utilizar un sistema de prueba interactivo para decidir si una cadena es miembro de un lenguaje en tiempo polinomial, aunque la prueba PSPACE tradicional pueda ser exponencialmente larga.

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 polinómica. Ahora, podemos definir:

${\displaystyle \Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j}]=\max \nolimits _{P}\Pr \left[V\leftrightarrow P{\text{ accepts }}w{\text{ starting at }}M_{j}\right]}$

y para cada 0 ≤ j ≤ p y cada historial de mensajes M _j , definimos inductivamente la función N _{M j} :

${\displaystyle N_{M_{j}}={\begin{cases}0&j=p{\text{ and }}m_{p}={\text{reject}}\\1&j=p{\text{ and }}m_{p}={\text{accept}}\\\max _{m_{j+1}}N_{M_{j+1}}&j<p{\text{ and }}j{\text{ is odd}}\\{\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}&j<p{\text{ and }}j{\text{ is even}}\\\end{cases}}}$

dónde:

${\displaystyle {\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}:=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}[V(w,r,M_{j})=m_{j+1}]N_{M_{j+1}}}$

donde Pr _r es la probabilidad tomada 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 ₀ como la secuencia de mensajes vacía, aquí demostraremos que N _{M 0} se puede calcular en el 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 recursión 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 inducción para probar esto de la siguiente manera.

Debemos demostrar que para cada 0 ≤ j ≤ p y cada M _j , N _{M j} = Pr[ V acepta w a partir de M _j ], y lo haremos mediante inducción sobre j . El caso base es demostrar para j = p . Luego, utilizaremos la inducción para ir desde p hasta 0.

El caso base de j = p es bastante simple. Dado que m _p es aceptado o rechazado, si m _p es aceptado, N _{M p} se define como 1 y Pr[ V acepta w a partir de M _j ] = 1, ya que el flujo de mensajes indica aceptación, por lo que la afirmación es verdadera. Si m _p es rechazado, el argumento es muy similar.

Para la hipótesis inductiva, suponemos que para algún j +1 ≤ p y cualquier secuencia de mensajes M _j+1 , N _{M j+1} = Pr[ V acepta w a partir de M _j+1 ] y luego demostramos 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 . Por la definición de N _{M j} ,

${\displaystyle N_{M_{j}}=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\left[V(w,r,M_{j})=m_{j+1}\right]N_{M_{j+1}}.}$

Entonces, por la hipótesis inductiva, podemos decir que esto es igual a

${\displaystyle \sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\left[V(w,r,M_{j})=m_{j+1}\right]*\Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right].}$

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,

${\displaystyle N_{M_{j}}=\max \nolimits _{m_{j+1}}N_{M_{j+1}}.}$

Entonces, por la hipótesis inductiva, esto es igual a

${\displaystyle \max \nolimits _{m_{j+1}}*\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}].}$

Esto es igual a Pr[ V acepta w a partir de M _j ] ya que:

${\displaystyle \max \nolimits _{m_{j+1}}\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}]\leq \Pr[V{\text{ accepts w starting at }}M_{j}]}$

porque el demostrador del lado derecho podría enviar el mensaje m _j+1 para maximizar la expresión del lado izquierdo. Y:

${\displaystyle \max \nolimits _{m_{j+1}}\Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right]\geq \Pr \left[V{\text{ accepts }}w{\text{ starting at }}M_{j}\right]}$

Dado que el mismo Probador no puede hacer nada mejor que enviar el mismo mensaje, esto se cumple independientemente de que i sea par o impar y la prueba de que IP ⊆ PSPACE está completa.

Aquí hemos construido una máquina de espacio polinomial que utiliza el mejor demostrador P para una cadena particular w en el lenguaje A. Utilizamos este mejor demostrador en lugar de un demostrador con bits de entrada aleatorios porque podemos probar cada conjunto de bits de entrada aleatorios en el espacio polinomial. Como hemos simulado un sistema de prueba interactivo con una máquina de espacio polinomial, hemos demostrado que IP ⊆ PSPACE , como se deseaba.

Espacio personal ⊆ IP

Para ilustrar la técnica que se utilizará para demostrar que PSPACE ⊆ IP , primero demostraremos un teorema más débil, que fue demostrado por Lund, et al.: #SAT ∈ IP . Luego, utilizando los conceptos de esta prueba, lo ampliaremos para mostrar que TQBF ∈ IP . Dado que TQBF ∈ PSPACE -completo y TQBF ∈ IP , entonces PSPACE ⊆ IP .

#SAT es miembro de IP

Comenzamos mostrando que #SAT está en IP , donde:

${\displaystyle \#{\text{SAT}}=\left\{\langle \varphi ,k\rangle \ :\ \varphi {\text{ is a CNF-formula with exactly }}k{\text{ satisfying assignments}}\right\}.}$

Tenga en cuenta que esto es diferente de la definición normal de #SAT , ya que es un problema de decisión, en lugar de una función.

Primero usamos aritmetización para mapear la fórmula booleana con n variables, φ( b ₁ , ..., b _n ) a un polinomio p _φ ( x ₁ , ..., x _n ), donde p _φ imita a φ en que 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 tabla a continuación.

A modo de ejemplo, se convertiría en un polinomio de la siguiente manera: ${\displaystyle \phi =a\land (b\lor \neg c)}$

${\displaystyle {\begin{aligned}p_{\varphi }&=a\wedge (b\vee \neg c)\\&=a\wedge \left(b*(1-c)\right)\\&=a\wedge \left(1-(1-b)(1-(1-c))\right)\\&=a\left(1-(1-b)(1-(1-c))\right)\\&=a-(ac-abc)\end{aligned}}}$

Las operaciones ab y a ∗ b dan como resultado cada una un polinomio con un grado limitado por la suma de los grados de los polinomios para a y b y, por lo tanto, el grado de cualquier variable es como máximo la longitud de φ.

Sea ahora F un cuerpo finito con orden q > 2 ⁿ ; exija también 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 única variable : Para 0 ≤ i ≤ n y para sea ${\displaystyle a_{1},\dots ,a_{i-1}\in F}$ ${\displaystyle a_{i}\in F}$ ${\displaystyle a_{1},\dots ,a_{i}\in F}$

${\displaystyle f_{i}(a_{1},\dots ,a_{i})=\sum \nolimits _{a_{i+1},\dots ,a_{n}\in \{0,1\}}p(a_{1},\dots ,a_{n}).}$

Tenga en cuenta que el valor de f ₀ es el número de asignaciones satisfactorias de φ. f ₀ es una función vacía, sin variables.

Ahora el protocolo para #SAT funciona de la siguiente manera:

• Fase 0 : El probador P elige un primo q > 2 ⁿ y calcula f ₀ , luego envía q y f ₀ al verificador V . V verifica que q es un primo mayor que max(1000, 2 ⁿ ) y que f ₀ () = k .
• Fase 1 : P envía los coeficientes de f ₁ ( z ) como un polinomio en z. V verifica que el grado de f ₁ sea menor que n y que f ₀ = f ₁ (0) + f ₁ (1). (Si no, V rechaza). V envía ahora un número aleatorio r ₁ de F a P .
• Fase i : P envía los coeficientes de como polinomio en z . V verifica que el grado de f _i sea menor que n y que . (Si no, V rechaza ). V envía ahora un número aleatorio r _i de F a P. ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)}$ ${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})=f_{i}(r_{1},\dots ,r_{i-1},0)+f_{i}(r_{1},\dots ,r_{i-1},1)}$
• Fase n+1 : V se evalúa para comparar con el valor . Si son iguales, V acepta; de lo contrario, V rechaza. ${\displaystyle p(r_{1},\dots ,r_{n})}$ ${\displaystyle f_{n}(r_{1},\dots ,r_{n})}$

Tenga en cuenta que este es un algoritmo de moneda pública.

Si φ tiene k asignaciones satisfactorias, claramente V lo aceptará. Si φ no tiene k asignaciones satisfactorias, suponemos que hay un probador que intenta convencer a V de que φ sí tiene k asignaciones satisfactorias. Demostramos que esto solo se puede hacer con baja probabilidad. ${\displaystyle {\tilde {P}}}$

Para evitar que V rechace en la fase 0, debe enviar un valor incorrecto a P . Luego, en la fase 1, debe enviar un polinomio incorrecto con la propiedad de que . Cuando V elige un r ₁ aleatorio para enviar a P , ${\displaystyle {\tilde {P}}}$ ${\displaystyle {\tilde {f}}_{0}()}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle {\tilde {f}}_{1}}$ ${\displaystyle {\tilde {f}}_{1}(0)+{\tilde {f}}_{1}(1)={\tilde {f}}_{0}()}$

${\displaystyle \Pr \left[{\tilde {f}}_{1}(r_{1})=f_{1}(r_{1})\right]<{\tfrac {1}{n^{2}}}.}$

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 evalúe a 0). Por lo tanto, dos polinomios cualesquiera en una sola variable de grado d como máximo pueden ser iguales solo en d lugares. Como | F | > 2 ⁿ las probabilidades de que r ₁ sea uno de estos valores son como máximo si n > 10, o como máximo ( n /1000) ≤ ( n / n ³ ) si n ≤ 10. ${\displaystyle n/2^{n}<n/n^{3}}$

Generalizando esta idea para las demás fases tenemos para cada 1 ≤ i ≤ n si

${\displaystyle {\tilde {f}}_{i-1}(r_{1},\dots ,r_{i-1})\neq f_{i-1}(r_{1},\dots ,r_{i-1}),}$

entonces para r _i elegido aleatoriamente de F ,

${\displaystyle \Pr \left[{\tilde {f}}(r_{1},\dots ,r_{i})=f_{i}(r_{1},\dots ,r_{i})\right]\leq {\tfrac {1}{n^{2}}}.}$

Existen n fases, por lo que la probabilidad de que sea afortunada porque V selecciona en alguna etapa un r _i conveniente es como máximo 1/ n . Por lo tanto, ningún demostrador puede hacer que el verificador acepte con una probabilidad mayor que 1/ n . También podemos ver a partir de la definición que el verificador V opera en tiempo polinomial probabilístico. Por lo tanto, #SAT ∈ IP . ${\displaystyle {\tilde {P}}}$

TQBF es miembro de IP

Para demostrar que PSPACE es un subconjunto de IP , debemos elegir un problema PSPACE-completo y demostrar que está en IP . Una vez que demostremos esto, queda claro que PSPACE ⊆ IP . La técnica de prueba que se muestra aquí se atribuye a Adi Shamir .

Sabemos que TQBF está en PSPACE-Complete . Por lo tanto, sea ψ una expresión booleana cuantificada:

${\displaystyle \psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]}$

donde φ es una fórmula CNF. Entonces Q _i es un cuantificador, ya sea ∃ o ∀. Ahora f _i es lo mismo que en la prueba anterior, pero ahora también incluye cuantificadores.

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i}(a_{1},\dots ,a_{m})=1&{\mathsf {Q}}_{i+1}x_{i+1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi (a_{1},\dots ,a_{i})]{\text{ is true}}\\0&{\text{otherwise}}\end{cases}}}$

Aquí, φ( a ₁ , ..., a _i ) es φ con a ₁ a a _i sustituido por x ₁ a x _i . Por lo tanto, f ₀ es el valor de verdad de ψ. Para aritmetizar ψ debemos utilizar las siguientes reglas:

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\forall \\f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\exists \end{cases}}}$

donde como antes definimos x ∗ y = 1 − (1 −  x )(1 −  y ).

Al utilizar el método descrito en #SAT, nos enfrentamos a un problema en el que, para cualquier f _i, el grado del polinomio resultante puede duplicarse con cada cuantificador. Para evitarlo, debemos introducir un nuevo operador de reducción R que reducirá los grados del polinomio sin cambiar su comportamiento en las entradas booleanas.

Ahora bien, antes de realizar la aritmética, introducimos una nueva expresión: ${\displaystyle \psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]}$

${\displaystyle \psi '={\mathsf {Q}}_{1}\mathrm {R} x_{1}{\mathsf {Q}}_{2}\mathrm {R} x_{1}\mathrm {R} x_{2}\dots {\mathsf {Q}}_{m}\mathrm {R} x_{1}\dots \mathrm {R} x_{m}[\varphi ]}$

o dicho de otra manera:

${\displaystyle \psi '={\mathsf {S}}_{1}y_{1}\dots {\mathsf {S}}_{k}y_{k}[\varphi ],\qquad {\text{ where }}{\mathsf {S}}_{i}\in \{\forall ,\exists ,\mathrm {R} \},\ y_{i}\in \{x_{1},\dots ,x_{m}\}}$

Ahora, para cada i ≤ k, definimos la función f _i . También la definimos como el polinomio p ( x ₁ , ..., x _m ) que se obtiene al aritmetizar φ. Ahora, para mantener bajo el grado del polinomio, definimos f _i en términos de f _i+1 : ${\displaystyle f_{k}(x_{1},\dots ,x_{m})}$

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\forall ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)}$

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\exists ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)}$

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\mathrm {R} ,\quad f_{i}(a_{1},\dots ,a_{i},a)=(1-a)f_{i+1}(a_{1},\dots ,a_{i},0)+af_{i+1}(a_{1},\dots ,a_{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. Por lo tanto, f ₀ sigue siendo el valor de verdad de ψ, pero el valor R _x produce un resultado que es lineal en x . Además, después de cualquier sumamos ψ′ para reducir el grado a 1 después de aritmetizar . ${\displaystyle {\mathsf {Q}}_{i}x_{i}}$ ${\displaystyle \mathrm {R} _{x_{1}}\dots \mathrm {R} _{x_{i}}}$ ${\displaystyle {\mathsf {Q}}_{i}}$

Ahora describamos el protocolo. Si n es la longitud de ψ, todas las operaciones aritméticas del protocolo se realizan sobre un campo de tamaño al menos n ⁴ , donde n es la longitud de ψ.

• Fase 0 : P → V : P envía f ₀ a V. V comprueba que f 0 = 1 y rechaza si no es _así .
• Fase 1 : P → V : P envía f ₁ ( z ) a V. V utiliza coeficientes para evaluar f ₁ (0) y f ₁ (1) . Luego, verifica que el grado del polinomio sea como máximo n y que las siguientes identidades sean verdaderas:

${\displaystyle f_{0}(\varnothing )={\begin{cases}f_{1}(0)\cdot f_{1}(1)&{\text{ if }}{\mathsf {S}}=\forall \\f_{1}(0)*f_{1}(1)&{\text{ if }}{\mathsf {S}}=\exists .\\(1-r)f_{1}(0)+rf_{1}(1)&{\text{ if }}{\mathsf {S}}=\mathrm {R} .\end{cases}}}$

Si alguno falla, rechácelo.

• Fase i : P → V : P se envía como un polinomio en z . r ₁ denota los valores aleatorios previamente establecidos para ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)}$ ${\displaystyle r_{1},\dots ,r_{i-1}}$

V utiliza coeficientes para evaluar y . Luego verifica que el grado del polinomio sea como máximo n y que las siguientes identidades sean verdaderas: ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},0)}$ ${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},1)}$

${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})={\begin{cases}f_{i}(r_{1},\dots ,r_{i-1},0)\cdot f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\forall \\f_{i}(r_{1},\dots ,r_{i-1},0)*f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\exists .\end{cases}}}$

${\displaystyle f_{i-1}(r_{1}\dots r)=(1-r)f_{i}(r_{1},\dots ,r_{i-1},0)+rf_{i}(r_{1},\dots ,r_{i-1},1){\text{ if }}{\mathsf {S}}=\mathrm {R} .}$

Si alguno falla, rechácelo.

V → P : V elige un r aleatorio en F y lo envía a P. (Si entonces este r reemplaza al r anterior ). ${\displaystyle {\mathsf {S}}=\mathrm {R} }$

Pasamos a la fase i  + 1 donde P debe convencer a V de que tiene razón. ${\displaystyle f_{i}(r_{1},\dots ,r)}$

• Fase k + 1 : V evalúa . Luego verifica si son iguales, V acepta; de lo contrario, V rechaza. ${\displaystyle p(r_{1},\dots ,r_{m})}$ ${\displaystyle p(r_{1},\dots ,r_{m})=f_{k}(r_{1},\dots ,r_{m})}$

Este es el final de la descripción del protocolo.

Si ψ es verdadero, entonces V aceptará cuando P siga el protocolo. Del mismo modo, si es un demostrador malicioso que miente, y si ψ es falso, entonces necesitará mentir en la fase 0 y enviar algún valor para f ₀ . Si en la fase i , V tiene un valor incorrecto para entonces y probablemente también será incorrecto, y así sucesivamente. La probabilidad de tener suerte en algún r aleatorio es como máximo el grado del polinomio dividido por el tamaño del campo: . El protocolo se ejecuta a través de O ( n ² ) fases, por lo que la probabilidad de que tenga suerte en alguna fase es ≤ 1/ n . Si nunca tiene suerte, entonces V rechazará en la fase k +1. ${\displaystyle {\tilde {P}}}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle f_{i-1}(r_{1},\dots )}$ ${\displaystyle f_{i}(r_{1},\dots ,0)}$ ${\displaystyle f_{i}(r_{1},\dots ,1)}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle n/n^{4}}$ ${\displaystyle {\tilde {P}}}$ ${\displaystyle {\tilde {P}}}$

Como hemos demostrado que tanto IP ⊆ PSPACE como PSPACE ⊆ IP , podemos concluir que IP = PSPACE como se deseaba. Además, hemos demostrado que cualquier algoritmo IP puede considerarse moneda pública, ya que la reducción de PSPACE a IP tiene esta propiedad.

Variantes

Existen diversas variantes de IP que modifican ligeramente la definición del sistema de prueba interactivo. Aquí resumimos algunas de las más conocidas.

aderezo

Un subconjunto de IP es la clase determinista Interactive Proof , que es similar a IP 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 las cadenas del lenguaje con el requisito de que siempre tenga éxito:

${\displaystyle w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]=1}$

Este criterio aparentemente más fuerte de "completitud perfecta" no cambia la clase de complejidad IP , ya que a cualquier lenguaje con un sistema de prueba interactivo se le puede dar un sistema de prueba interactivo con completitud perfecta. ^[4]

PMI

En 1988, Goldwasser et al. crearon 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 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 si hay otro probador con el que puede 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 lenguajes en NP tienen pruebas de conocimiento cero en un sistema MIP , sin ningún supuesto adicional; esto solo se conoce para IP asumiendo la existencia de funciones unidireccionales.

PPI

IPP ( IP sin límites ) 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:

• Completitud : si una cadena está en el lenguaje, el verificador honesto estará convencido de este hecho por un demostrador honesto con una probabilidad de al menos 1/2.
• Solidez : si la cadena no está en el lenguaje, ningún demostrador puede convencer al verificador honesto de que está en el lenguaje, 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 al verificador BPP por un verificador BQP , donde BQP es la clase de problemas que pueden resolver los ordenadores cuánticos en tiempo polinomial. Los mensajes están compuestos por 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 potencia adicional al protocolo. Esto subsume un resultado previo 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 otorgan más poder al verificador, un sistema compIP ( sistema de prueba de IP competitivo ) debilita la condición de completitud de una manera que debilita al probador:

• Completitud : si una cadena está en el lenguaje L , el verificador honesto se convencerá de este hecho por un probador honesto con una probabilidad de al menos 2/3. Además, el probador lo hará en tiempo polinomial probabilístico dado el acceso a un oráculo para el lenguaje L.

Básicamente, esto convierte al probador en una máquina BPP con acceso a un oráculo para el lenguaje, pero solo en el caso de completitud, no en el caso de solidez. El concepto es que si un lenguaje está en compIP , entonces probarlo interactivamente 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 algo. De hecho, ni siquiera se sabe o se cree que compIP contenga NP .

Por otra parte, un sistema de este tipo puede resolver algunos problemas que se consideran difíciles. Resulta un tanto paradójico que, aunque no se crea que un sistema de este tipo pueda resolver todos los problemas NP , pueda resolver fácilmente todos los problemas NP-completos debido a la autorreducibilidad. Esto se debe al hecho de que si el lenguaje L no es NP -duro, el demostrador tiene un poder sustancialmente limitado (ya que ya no puede decidir todos los problemas NP con su oráculo).

Además, el problema de no isomorfismo de grafos (que es un problema clásico en IP ) también está en compIP , ya que la única operación difícil que el probador tiene que hacer es la prueba de isomorfismo, que puede usar el oráculo para resolver. La no-residuosidad cuadrática y el isomorfismo de grafos también están en compIP . ^[9] Nótese que la no-residuosidad cuadrática (QNR) es probablemente un problema más fácil que el isomorfismo de grafos ya que QNR está en UP intersect co-UP . ^[10]

Notas

1. Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N. (1990). "Métodos algebraicos para sistemas de prueba interactivos". Actas [1990] 31.° Simposio anual sobre fundamentos de la informática . IEEE Comput. Soc. Press. págs. 2–10. doi :10.1109/fscs.1990.89518. ISBN . 0-8186-2082-X. Número de identificación del sujeto  32614901.
2. Shamir, Adi. "Ip= espacio". Revista de la ACM 39.4 (1992): 869-877.
3. Chang Richard; et al. (1994). "La hipótesis del oráculo aleatorio es falsa". Journal of Computer and System Sciences . 49 (1): 24–39. doi : 10.1016/s0022-0000(05)80084-4 .
4. Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis (1989). "Sobre completitud y solidez en sistemas de prueba interactivos". Avances en investigación informática: un anuario de investigación . 5 : 429–442. CiteSeerX 10.1.1.39.9412 . {{cite journal}}: CS1 maint: multiple names: authors list (link)
5. 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 de Sistemas , 49(1):24-39. 1994.
6. J. Watrous. PSPACE tiene sistemas de prueba interactivos cuánticos de ciclo constante. Actas de IEEE FOCS'99 , págs. 112-119. 1999.
7. Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (2009). "QIP = ESPACIO". arXiv : 0907.4737 [cuántico-ph].
8. A. Kitaev y J. Watrous. Paralelización, amplificación y simulación temporal 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.
9. Shafi Goldwasser y Mihir Bellare . La complejidad de la decisión frente a la búsqueda. Revista SIAM de Computación , Volumen 23, N° 1. Febrero de 1994.
10. Cai JY, Threlfall RA (2004). "Una nota sobre residuosidad cuadrática y UP ". Information Processing Letters . 92 (3): 127–131. CiteSeerX 10.1.1.409.1830 . doi :10.1016/j.ipl.2004.06.015. 

Referencias

• Babai, L. Intercambio de teoría de grupos por aleatoriedad. En Actas del 17.º Simposio de la 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 ACM sobre la teoría de la computación , Providence, Rhode Island. 1985, págs. 291-304. Resumen ampliado. Archivado el 23 de junio de 2006 en Wayback Machine.
• Shafi Goldwasser y Michael Sipser. Monedas privadas versus monedas públicas en sistemas de prueba interactivos. Actas del 18.° Simposio Anual de la 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 = ESPACIO. [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. Revista de la ACM , volumen 39, número 4, págs. 869–877. Octubre de 1992.
• Alexander Shen. IP=PSpace: Prueba simplificada. J.ACM, v. 39(4), págs. 878–880, 1992.
• Complexity Zoo : IP, MIP Archivado el 3 de junio de 2013 en Wayback Machine , IPP Archivado el 3 de junio de 2013 en Wayback Machine , QIP Archivado el 14 de marzo de 2014 en Wayback Machine , QIP(2) Archivado el 14 de marzo de 2014 en Wayback Machine , compIP Archivado el 21 de mayo de 2013 en Wayback Machine , frIP Archivado el 3 de junio de 2013 en Wayback Machine