Prueba comprobable probabilísticamente

En la teoría de la complejidad computacional, una prueba comprobable probabilísticamente (PCP) es un tipo de prueba que puede comprobarse mediante un algoritmo aleatorio utilizando una cantidad limitada de aleatoriedad y lectura. un número limitado de bits de la prueba. Luego se requiere que el algoritmo acepte pruebas correctas y rechace pruebas incorrectas con una probabilidad muy alta. Una prueba (o certificado) estándar, tal como se utiliza en la definición de la clase de complejidad NP basada en el verificador, también satisface estos requisitos, ya que el procedimiento de verificación lee de manera determinista toda la prueba, siempre acepta las pruebas correctas y rechaza las pruebas incorrectas. Sin embargo, lo que los hace interesantes es la existencia de pruebas comprobables probabilísticamente que pueden verificarse leyendo sólo unos pocos fragmentos de la prueba utilizando la aleatoriedad de manera esencial.

Las pruebas comprobables probabilísticamente dan lugar a muchas clases de complejidad dependiendo del número de consultas requeridas y de la cantidad de aleatoriedad utilizada. La clase PCP[r(n),q(n)] se refiere al conjunto de problemas de decisión que tienen pruebas comprobables probabilísticamente que pueden verificarse en tiempo polinomial utilizando como máximo r(n) bits aleatorios y leyendo como máximo q (n) bits de la prueba. A menos que se especifique lo contrario, siempre se deben aceptar las pruebas correctas y las pruebas incorrectas deben rechazarse con una probabilidad superior a 1/2. El teorema PCP, un resultado importante en la teoría de la complejidad computacional, establece que PCP[O(log n),O(1)] = NP.

Definición

Dado un problema de decisión L (o un idioma L con su conjunto alfabético Σ), un sistema de prueba comprobable probabilísticamente para L con integridad c(n) y solidez s(n), donde 0 ≤ s (n) ≤ c(n) ≤ 1, consta de un probador y un verificador. Dada una solución x con longitud n, que podría ser falsa, el probador produce una prueba π que establece que x resuelve L (x ∈ < i>L, la prueba es una cadena ∈ Σ^*). Y el verificador es una Máquina de Turing oráculo aleatoria V (el verificador) que verifica la prueba π de la afirmación de que x resuelve L(o x ∈ L) y decide si acepta la declaración. El sistema tiene las siguientes propiedades:

• CompletenessPara cualquier x ▪ L, dada la prueba π producido por el probador del sistema, el verificador acepta la declaración con probabilidad al menos c()n),
• SonidoPara cualquier x ∉ L, entonces para cualquier prueba π, el verificador acepta erróneamente la declaración con probabilidad a la mayoría s()n).

Para la complejidad computacional del verificador, tenemos la complejidad de aleatoriedad r(n) para medir el número máximo de bits aleatorios que V utiliza sobre todo x de longitud n y la complejidad de consulta q(< i>n) del verificador es el número máximo de consultas que V realiza a π en todo x de longitud n.

En la definición anterior, la duración de la prueba no se menciona ya que normalmente incluye el conjunto de letras y todos los testigos. Para el demostrador, no nos importa cómo llega a la solución del problema; sólo nos importa la prueba que da de la pertenencia de la solución al lenguaje.

Se dice que el verificador es no adaptativo si realiza todas sus consultas antes de recibir cualquiera de las respuestas a consultas anteriores.

La clase de complejidad PCP_{c(n), s(n)}[r(n), q(n)] es la clase de todos los problemas de decisión que tienen sistemas de prueba comprobables probabilísticamente sobre el alfabeto binario de completitud c(n) y solidez s(n), donde el verificador no es adaptativo, se ejecuta en tiempo polinómico y tiene complejidad de aleatoriedad r(n) y complejidad de consulta q(< en>n).

La notación abreviada PCP[r(n), q(n)] a veces se utiliza para PCP_{1, ½}[r(n), q(n)]. La clase de complejidad PCP se define como PCP_{1, ½}[O(log n), O(1) ].

Historia y significado

La teoría de las pruebas comprobables probabilísticamente estudia el poder de los sistemas de prueba comprobables probabilísticamente bajo diversas restricciones de los parámetros (integridad, solidez, complejidad de la aleatoriedad, complejidad de la consulta y tamaño del alfabeto). Tiene aplicaciones para la complejidad computacional (en particular, la dureza de aproximación) y la criptografía.

La definición de prueba comprobable probabilísticamente fue introducida explícitamente por Arora y Safra en 1992, aunque sus propiedades se estudiaron antes. En 1990, Babai, Fortnow y Lund demostraron que PCP[poly(n), poli(n)] = NEXP, proporcionando la primera equivalencia no trivial entre pruebas estándar (NEXP) y pruebas comprobables probabilísticamente. El teorema de PCP demostrado en 1992 establece que PCP[O(log n),O(1)] = NP.

La teoría de la dureza de la aproximación requiere una comprensión detallada del papel de la integridad, la solidez, el tamaño del alfabeto y la complejidad de la consulta en pruebas comprobables probabilísticamente.

Propiedades

Desde el punto de vista de la complejidad computacional, para configuraciones extremas de los parámetros, la definición de pruebas comprobables probabilísticamente se considera fácilmente equivalente a las clases de complejidad estándar. Por ejemplo, tenemos lo siguiente para diferentes configuraciones de PCP[r(n), q(n)]:

• PCP[0, 0] = P ()P se define para no tener aleatoriedad ni acceso a una prueba.)
• PCP[O(log)n)), 0] = P (Un número logarítmico de bits aleatorios no ayuda a un tiempo polinomio Máquina de Turing, ya que podría probar todas las cadenas posiblemente aleatorias de longitud logarítmica en tiempo polinomio.)
• PCP[0,O(log(n)] = P (Sin azar, la prueba se puede considerar como una cadena de tamaño logarítmico fijo. Una máquina de tiempo polinomio podría probar todas las pruebas de tamaño logarítmico posibles en tiempo polinomio.)
• PCP[pobre]n), 0] = coRP (Definición de coRP.)
• PCP[0, poli(n) = NP (Por la definición basada en el verificador de NP.)

El teorema PCP y MIP = NEXP se pueden caracterizar de la siguiente manera:

• PCP[O(log) n),O(1)] =NP (el teorema PCP)
• PCP[pobre]n),O(1)] =PCP[pobre]n),poly(n) =NEXP (MIP = NEXP).

También se sabe que PCP[r(n), q(n)] ⊆ NTIME(poly(n,2^O(r(n))q(n))). En particular, PCP[log n, poli(n)] = NP. Por otro lado, si NP ⊆ PCP[o(log n),o(log n)] entonces P = NP.

PCP lineal

Un PCP lineal es un PCP en el que la prueba es un vector de elementos de un campo finito ${displaystyle pi in mathbb {F} {n}$, y tal que el oráculo PCP sólo se permite hacer operaciones lineales en la prueba. Es decir, la respuesta del oráculo a una consulta verificadora ${displaystyle qin mathbb {fn}$ es una función lineal ${displaystyle f(q,pi)}$. Los PCP lineales tienen aplicaciones importantes en sistemas de prueba que se pueden compilar en SNARKs.