Prueba verificable probabilísticamente

En la teoría de la complejidad computacional , una prueba verificable probabilísticamente ( PCP ) es un tipo de prueba que puede verificarse mediante un algoritmo aleatorio que utiliza una cantidad limitada de aleatoriedad y lee un número limitado de bits de la prueba. El algoritmo debe aceptar las pruebas correctas y rechazar las incorrectas con una probabilidad muy alta. Una prueba estándar (o certificado ), como se utiliza en la definición de la clase de complejidad NP basada en verificadores , también satisface estos requisitos, ya que el procedimiento de verificación lee deterministamente toda la prueba, acepta siempre las correctas y rechaza las incorrectas. Sin embargo, lo que las hace interesantes es la existencia de pruebas verificables probabilísticamente que pueden verificarse leyendo solo unos pocos bits de la prueba mediante la aleatoriedad de forma esencial.

Las pruebas verificables probabilísticamente 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 verificables probabilísticamente que pueden verificarse en tiempo polinomial usando 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 (un lenguaje sobre un alfabeto Σ), un sistema de prueba probabilísticamente verificable 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 supuesta solución x de longitud n , que podría ser falsa, el probador produce una prueba π que afirma que x resuelve L ( x ∈ L , la prueba es una cadena en Σ ^* ). Y el verificador es una máquina de Turing oráculo aleatoria V (el verificador ) que comprueba 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:

• Completitud : Para cualquier x ∈ L , dada la prueba π producida por el probador del sistema, el verificador acepta la afirmación con una probabilidad de al menos c ( n ),
• Solidez : Para cualquier x ∉ L , entonces para cualquier prueba π , el verificador acepta erróneamente la afirmación con una probabilidad como máximo s ( n ).

En cuanto a la complejidad computacional del verificador, este tiene un tiempo polinomial, y tenemos la complejidad de aleatoriedad r ( n ) para medir el número máximo de bits aleatorios que V utiliza sobre todos los x de longitud n, y la complejidad de consulta q ( n ) del verificador es el número máximo de consultas que V realiza a π sobre todos los x de longitud n .

En la definición anterior, no se menciona la longitud de la prueba, ya que generalmente incluye el conjunto del alfabeto y todos los testigos. Para el probador, no importa cómo llega a la solución del problema; solo nos importa la prueba que ofrece de que la solución pertenece 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 verificables 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 usa 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 verificables probabilísticamente estudia la potencia de los sistemas de pruebas verificables probabilísticamente 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, la dificultad de la aproximación ) y la criptografía .

La definición de una prueba verificable probabilísticamente fue introducida explícitamente por Arora y Safra en 1992, ^{[ 2 ]} aunque sus propiedades se estudiaron con anterioridad. 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 verificables probabilísticamente. ^{[ 3 ]} El teorema PCP demostrado en 1992 establece que PCP [ O (log n ), O (1)] = NP . ^{[ 2 ] [ 4 ]}

La teoría de la dificultad de la aproximación requiere una comprensión detallada del papel que desempeñan la completitud, la solidez, el tamaño del alfabeto y la complejidad de la consulta en las pruebas verificables probabilísticamente.

Desde el punto de vista de la complejidad computacional, para configuraciones extremas de los parámetros, la definición de pruebas verificables probabilísticamente se ve 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 como sin aleatoriedad y sin acceso a una prueba).
• PCP [ O (log n ), 0] = P (Un número logarítmico de bits aleatorios no ayuda a una máquina de Turing de tiempo polinomial, ya que podría probar todas las cadenas aleatorias posibles de longitud logarítmica en tiempo polinomial).
• PCP [O(1), O (log n )] = P (Sin aleatoriedad, la prueba puede considerarse como una cadena de longitud logarítmica fija. Una máquina de tiempo polinomial podría probar todas las posibles pruebas de longitud logarítmica y cadenas aleatorias de longitud constante en tiempo polinomial).
• PCP [poly( n ), 0] = coRP (Por definición de coRP .)
• PCP [0, poly( n )] = NP (Según la definición de NP basada en verificadores).

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

• PCP [ O (log n ), O (1)] = NP (el teorema PCP)
• PCP [poly( n ), O (1)] = PCP [poly( 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 [O(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 campo finito.${\displaystyle \pi \in \mathbb {F} ^{n}}$y de tal manera que el oráculo PCP solo puede realizar operaciones lineales sobre la prueba. Es decir, la respuesta del oráculo a una consulta del verificador${\displaystyle q\in \mathbb {F} ^{n}}$es una función lineal${\displaystyle f(q,\pi )}$Los PCP lineales tienen aplicaciones importantes en sistemas de prueba que pueden compilarse en SNARKs.

• Prueba holográfica en la Enciclopedia de Matemáticas
• Apuntes del curso PCP de Subhash Khot en la Universidad de Nueva York , 2008.
• Apuntes del curso PCP y Una historia del teorema PCP por Ryan O'Donnell y Venkatesan Guruswami de la Universidad de Washington , 2005.
• Zoológico de la complejidad : PCP