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 que utiliza una cantidad limitada de aleatoriedad y lee 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 ), como se usa en la definición basada en verificador de la clase de complejidad NP , también satisface estos requisitos, ya que el procedimiento de verificación lee determinísticamente toda la prueba, siempre acepta pruebas correctas y rechaza pruebas incorrectas. Sin embargo, lo que las hace interesantes es la existencia de pruebas comprobables probabilísticamente que pueden comprobarse leyendo solo unos pocos bits de la prueba utilizando la aleatoriedad de manera esencial.
Las pruebas probabilísticamente comprobables dan lugar a muchas clases de complejidad dependiendo del número de consultas requeridas y la cantidad de aleatoriedad utilizada. La clase PCP [ r ( n ), q ( n )] se refiere al conjunto de problemas de decisión que tienen pruebas probabilísticamente comprobables 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. [1] A menos que se especifique lo contrario, las pruebas correctas siempre deben aceptarse y las pruebas incorrectas deben rechazarse con una probabilidad mayor que 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 .
Dado un problema de decisión L (o un lenguaje L con su conjunto de alfabetos Σ), un sistema de prueba probabilísticamente comprobable para L con completitud c ( n ) y solidez s ( n ), donde 0 ≤ s ( n ) ≤ c ( n ) ≤ 1 , consiste en un probador y un verificador. Dada una solución declarada x con longitud n, que podría ser falsa, el probador produce una prueba π que establece que x resuelve L ( x ∈ L , la prueba es una cadena ∈ Σ ∗ ). Y el verificador es una máquina de Turing oráculo aleatorizada V (el verificador ) que verifica la prueba π para la afirmación de que x resuelve L (o x ∈ L ) y decide si acepta la afirmación. 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 sobre 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 longitud de la prueba, ya que normalmente incluye el conjunto de letras y todos los testigos. Al demostrador no le 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 no es adaptativo si realiza todas sus consultas antes de recibir alguna de las respuestas a las 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 probabilísticamente comprobables 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 una complejidad de aleatoriedad r ( n ) y una 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 probabilísticamente comprobables estudia el poder de los sistemas de pruebas probabilísticamente comprobables bajo diversas restricciones de los parámetros (completitud, solidez, complejidad aleatoria, complejidad de la consulta y tamaño del alfabeto). Tiene aplicaciones en la complejidad computacional (en particular, en la dificultad de aproximación ) y en la criptografía .
La definición de una prueba probabilísticamente comprobable fue introducida explícitamente por Arora y Safra en 1992, [2] aunque sus propiedades se habían estudiado antes. En 1990 Babai, Fortnow y Lund demostraron que PCP [poly( n ), poly( n )] = NEXP , proporcionando la primera equivalencia no trivial entre pruebas estándar ( NEXP ) y pruebas probabilísticamente comprobables. [3] El teorema 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 completitud, 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, la definición de pruebas probabilísticamente comprobables es fácilmente 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 , poly( 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 cuerpo 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 de verificación es una función lineal . Los PCP lineales tienen aplicaciones importantes en sistemas de prueba que se pueden compilar en SNARK.
