En la teoría de la complejidad computacional , una prueba verificable probabilísticamente ( PCP ) es un tipo de prueba que se puede verificar 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 ), como se usa en la definición basada en el verificador de la clase de complejidad NP, también cumple con estos requisitos, ya que el procedimiento de verificación lee de manera determinista la prueba completa, siempre acepta las pruebas correctas y rechaza las pruebas incorrectas. Sin embargo, lo que los hace interesantes es la existencia de demostraciones comprobables probabilísticamente que pueden verificarse leyendo solo unos pocos fragmentos de la demostración usando la aleatoriedad de manera esencial.
Las pruebas comprobables probabilísticamente dan lugar a muchas clases de complejidad según el 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 comprobables probabilísticamente que se pueden verificar 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 superior a 1/2. El teorema del 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 idioma L con su conjunto alfabético Σ), un sistema de prueba comprobable probabilísticamente para L con completitud 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 probador produce una prueba π que establece que x resuelve L ( x ∈ L , la prueba es una cadena ∈ Σ * ). Y el verificador es un aleatorioOracle Turing Machine 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 utiliza V sobre todo x de longitud n y la complejidad de consulta q ( n ) del verificador es el número máximo de bits consultas que hace V a π sobre todo x de longitud n .
En la definición anterior, la longitud de la prueba no se menciona ya que generalmente incluye el conjunto alfabético y todos los testigos. Para el experimentador, 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 no es adaptativo si realiza todas sus consultas antes de recibir alguna de las respuestas a consultas anteriores.