En la teoría de la complejidad computacional , una prueba comprobable probabilísticamente ( PCP ) es un tipo de prueba que puede verificarse mediante un algoritmo aleatorio utilizando una cantidad limitada de aleatoriedad y leyendo 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 estándar (o certificado ), 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, acepta siempre 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 necesarias 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 polinómico utilizando como máximo r ( n ) bits aleatorios y leyendo como máximo q ( n ). ) fragmentos de la prueba. [1] 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 de PCP , un resultado importante en la teoría de la complejidad computacional, establece que PCP [ O (log n ), O (1)] = NP .
Dado un problema de decisión L (o un lenguaje 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 reclamada x con longitud n, que podría ser falsa, el demostrador produce una prueba π que establece que x resuelve L ( x ∈ L , la prueba es una cadena ∈ Σ ∗ ). Y el verificador es un oráculo aleatorio Máquina de Turing V (el verificador ) que verifica la prueba π del enunciado de que x resuelve L (o x ∈ L ) y decide si acepta el enunciado. El sistema tiene las siguientes propiedades:
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 usa en todo x de longitud n y la complejidad de consulta q ( n ) del verificador es el número máximo de consultas que V hace a π sobre todo x de longitud n .
En la definición anterior, no se menciona la duración de la prueba, ya que normalmente incluye el conjunto alfabético y todos los testigos. Para el demostrador, no nos importa cómo llega a la solución del problema; sólo nos preocupamos por la prueba que da de la pertenencia de la solución al idioma.
Se dice que el verificador no es adaptativo si realiza todas sus consultas antes de recibir alguna 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 un alfabeto binario de completitud c ( n ) y solidez s ( n ), donde el verificador no es adaptativo, se ejecuta en tiempo polinomial y tiene complejidad de aleatoriedad r ( n ) y complejidad de consulta q ( n ).
La notación abreviada PCP [ r ( n ), q ( n )] se utiliza a veces para PCP 1, 1/2 [ r ( n ), q ( n )] . La clase de complejidad PCP se define como PCP 1, 1/2 [ O (log n ), O (1)] .
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 probabilísticamente comprobable fue introducida explícitamente por Arora y Safra en 1992, [2] aunque sus propiedades se estudiaron antes. En 1990, Babai, Fortnow y Lund demostraron que PCP [poli( n ), poli( n )] = NEXP , proporcionando la primera equivalencia no trivial entre pruebas estándar ( NEXP ) y pruebas comprobables probabilísticamente. [3] El teorema de PCP demostrado en 1992 establece que PCP [ O (log n ), O (1)] = NP . [2] [4]
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.
Desde el punto de vista de la complejidad computacional, para configuraciones extremas de los parámetros, se considera fácilmente que la definición de pruebas comprobables probabilísticamente es equivalente a las clases de complejidad estándar . Por ejemplo, tenemos lo siguiente para diferentes configuraciones de PCP [ r ( n ), q ( n )]:
El teorema PCP y MIP = NEXP se pueden caracterizar de la siguiente manera:
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 . [2]
Un PCP lineal es un PCP en el que la prueba es un vector de elementos de un campo finito , y tal que el oráculo PCP solo puede realizar operaciones lineales en la prueba. Es decir, la respuesta del oráculo a una consulta del verificador es una función lineal . Los PCP lineales tienen aplicaciones importantes en sistemas de prueba que se pueden compilar en SNARK.
