IP (complejidad)

En la teoría de la complejidad computacional , la clase IP ( prueba interactiva ) 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 el co-NP tenía múltiples pruebas interactivas; ^[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 relativiza . ^[3]

El concepto de 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 algo de lenguaje y un verificador, V , que comprueba que la prueba presentada es correcta. Se supone que el probador es infinito en cálculo y almacenamiento, mientras que el verificador es una máquina probabilística de tiempo polinómico con acceso a una cadena de bits aleatoria cuya longitud es polinómica del tamaño de n . Estas dos máquinas intercambian un número polinómico, p ( n ), de mensajes y una vez completada la interacción, el verificador debe decidir si n está o no en el idioma, con solo 1/3 de probabilidad de error. (Por lo tanto, cualquier idioma en BPP está en IP , desde entonces el verificador podría simplemente ignorar al probador y tomar la decisión por sí solo).

Representación general de un protocolo de prueba interactivo.

Definición

Un lenguaje L pertenece a IP si existe V , P tal 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 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 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 usar un sistema de prueba interactivo para decidir si una cadena es miembro de un lenguaje en tiempo polinómico, aunque la prueba PSPACE tradicional puede ser exponencialmente largo.

Prueba de IP = PSPACE

La prueba se puede dividir en dos partes, demostramos que IP ⊆ PSPACE y PSPACE ⊆ IP .

IP ⊆ ESPACIO

Para demostrar que IP ⊆ PSPACE , presentamos una simulación de un sistema de prueba interactivo mediante una máquina espacial polinomial. 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í mostraremos 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 recursividad es p , sólo 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 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 comenzando en M _j ], y lo haremos usando inducción en j . El caso base es demostrar que j = p . Luego usaremos 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 rechazado, el argumento es muy similar.

Para la hipótesis inductiva, asumimos que para algún j +1 ≤ p y 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} ,

${\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 Mj ].

Si j es impar, m j ₊₁ es un mensaje de P a V. Por definición,

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

Entonces, según la hipótesis inductiva, esto es igual

${\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 comenzando en 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]}$

Ya que el mismo Probador no puede hacer nada mejor que enviar ese mismo mensaje. Por lo tanto, esto es válido tanto si i es par como impar y la prueba de que IP ⊆ PSPACE es completa.

Aquí hemos construido una máquina espacial polinómica que utiliza el mejor probador P para una cadena particular 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. Como hemos simulado un sistema de prueba interactivo con una máquina espacial polinomial, hemos demostrado que IP ⊆ PSPACE , como se desea.

ESPACIO ⊆ IP

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

#SAT es miembro del 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 , en que es un problema de decisión, en lugar de una función.

Primero usamos la 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 ese p _φ es 1 si φ es verdadero y 0 en caso contrario, siempre que a las variables de p _φ se les asigne valores booleanos. Las operaciones booleanas ∨, ∧ y ¬ utilizadas en φ se simulan en p _φ reemplazando los operadores en φ como se muestra en la siguiente tabla.

Como ejemplo, φ = a ∧ ( b ∨ ¬ c ) se convertiría en un polinomio de la siguiente manera:

${\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}}}$

Cada una de las operaciones ab y a ∗ b dan como resultado un polinomio con un grado acotado 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 φ.

Ahora sea F un cuerpo finito de orden q > 2 ⁿ ; 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 let ${\displaystyle a_{1},\dots ,a_{i-1}\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 comprueba 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 ₁ es menor que n y que f ₀ = f ₁ (0) + f ₁ (1). (Si no, V rechaza). V ahora envía un número aleatorio r ₁ de F a P.
• Fase i : P envía los coeficientes de como un polinomio en z . V verifica que el grado de f _i es menor que n y que . (Si no, V rechaza). V ahora envía 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, en caso 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 las aceptará. Si φ no tiene k asignaciones satisfactorias, asumimos que hay un demostrador que intenta convencer a V de que φ sí tiene k asignaciones satisfactorias. Demostramos que esto sólo se puede hacer con baja probabilidad. ${\displaystyle {\tilde {P}}}$

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 de que . Cuando V elige un r ₁ aleatorio para enviarlo 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 como máximo d 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 ⁿ la probabilidad de que r ₁ sea uno de estos valores es 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 otras 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 al azar 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}}}.}$

Hay n fases, por lo que la probabilidad de tener suerte porque V selecciona en algún momento un r _i conveniente es como máximo 1/ n . Entonces, ningún probador puede hacer que el verificador acepte con una probabilidad mayor que 1/ n . También podemos ver en la definición que el verificador V opera en tiempo polinómico probabilístico. Por tanto, #SAT ∈ IP . ${\displaystyle {\tilde {P}}}$

TQBF es miembro de IP

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

Sabemos que TQBF está en PSPACE-Complete . Entonces, 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 igual 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 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, 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.

Entonces, antes de aritmetizar, 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 definimos como el polinomio p ( x ₁ , ..., x _m ) que se obtiene aritmetizando φ. 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 las entradas booleanas. Entonces f ₀ sigue siendo el valor de verdad de ψ, pero el valor de R _x produce un resultado que es lineal en x . Además, después de any agregamos ψ′ 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 en el 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 ₀ = 1 y rechaza si no.
• Fase 1 : P → V : P envía f ₁ ( z ) a V. V utiliza coeficientes para evaluar f ₁ (0) y f ₁ (1). Luego se comprueba 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 de los dos falla, rechace.

• Fase i : P → V : P se envía como 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 usa coeficientes para evaluar y . Luego comprueba 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 de los dos falla, rechace.

V → P : V elige una r aleatoria en F y la envía a P. (Si entonces esta r reemplaza la r anterior ). ${\displaystyle {\mathsf {S}}=\mathrm {R} }$

Vaya a la fase i  + 1 donde P debe persuadir a V de que es correcto. ${\displaystyle f_{i}(r_{1},\dots ,r)}$

• Fase k +1 : V evalúa . Luego verifica si son iguales entonces 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 probador malicioso el 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 con algún r aleatorio es como máximo el grado del polinomio dividido por el tamaño del campo: . El protocolo pasa por O ( n ² ) fases, por lo que la probabilidad de tener suerte en alguna fase es ≤ 1/ n . Si nunca hay 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 ahora hemos demostrado que tanto IP ⊆ PSPACE como PSPACE ⊆ IP , podemos concluir que IP = PSPACE como se desee. Además, hemos demostrado que cualquier algoritmo IP puede considerarse una moneda pública, ya que la reducción de PSPACE a IP tiene esta propiedad.

Variantes

Existen varias variantes de IP que modifican ligeramente la definición del sistema de prueba interactivo. Resumimos aquí algunos de los más conocidos.

aderezo

Un subconjunto de IP es la clase determinista Prueba interactiva , que es similar a IP pero tiene un verificador determinista (es decir, sin aleatoriedad). Esta clase es igual a NP .

Perfecta integridad

Una definición equivalente de IP reemplaza la condición de que la interacción tenga éxito con alta probabilidad en 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 "integridad 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 integridad perfecta. ^[4]

PIM

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 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 si hay otro probador con quien pueda verificar. 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. Además, todos los idiomas en NP tienen pruebas de conocimiento cero en un sistema MIP , sin suposiciones adicionales; esto sólo se conoce para IP asumiendo la existencia de funciones unidireccionales.

PPI

IPP ( IP ilimitada ) es una variante de IP donde 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 una probabilidad de al menos 1/2.
• Solidez : si la cadena no está en el idioma, ningún probador puede convencer al verificador honesto de que sí está en el idioma, excepto con una probabilidad menor que 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 el verificador BPP por un verificador BQP , donde BQP es la clase de problemas que pueden resolver las computadoras cuánticas en tiempo polinomial. Los mensajes están compuestos 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 incluye 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 integridad de una manera que debilita al probador:

• Integridad : si una cadena está en el lenguaje L , el verificador honesto será convencido de este hecho por un probador honesto con una probabilidad de al menos 2/3. Además, el demostrador lo hará en tiempo polinómico probabilístico dado acceso a un oráculo para el lenguaje L.

Esencialmente, esto convierte al probador en una máquina BPP con acceso a un oráculo para el idioma, pero solo en el caso de que esté completo, no en el caso de que sea sólido. 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 ni se cree que compIP contenga NP .

Por otra parte, un sistema de este tipo puede resolver algunos problemas que se consideran difíciles. De manera un tanto paradójica, aunque no se cree que un sistema de este tipo sea capaz de resolver todos los NP , puede 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 poder del demostrador está sustancialmente limitado (ya que ya no puede decidir todos los problemas NP con su oráculo).

Además, el problema del no isomorfismo del 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 realizar el demostrador 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 la intersección UP 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 . Computación IEEE. Soc. Prensa. págs. 2–10. doi :10.1109/fscs.1990.89518. ISBN 0-8186-2082-X. S2CID  32614901.
2. Shamir, Adi. "Ip=pespacio." Revista de la ACM 39.4 (1992): 869-877.
3. Chang Richard; et al. (1994). "La hipótesis del oráculo aleatorio es falsa". Revista de Ciencias de la Computación y de Sistemas . 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 la integridad y solidez de los sistemas de prueba interactivos". Avances en la investigación en 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 ronda constante. Actas de IEEE FOCS'99 , págs. 112-119. 1999.
7. Rahul Jainista; 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 de tiempo exponencial de sistemas de prueba cuánticos interactivos. Actas del 32º Simposio ACM sobre Teoría de la Computación , págs. 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 ". 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 del grupo comercial 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 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 = 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 = ESPACIO. Revista de la ACM , volumen 39, número 4, p. 869–877. Octubre de 1992.
• Alejandro 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 3 de marzo de 2014 14 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