Prueba comprobable probabilísticamente

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Por favor, ayude a mejorar este artículo introduciendo citas más precisas. ( Noviembre de 2012 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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:

• Completitud : Para cualquier x ∈ L , dada la prueba π producida por el demostrador del sistema, el verificador acepta la afirmación con una probabilidad al menos c ( n ),
• Solidez : Para cualquier x ∉ L , entonces, para cualquier prueba π , el verificador acepta erróneamente la afirmación con probabilidad como máximo 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 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 )]:

• 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 posiblemente aleatorias de longitud logarítmica en tiempo polinomial).
• PCP [0, O (log( n ))] = P (Sin aleatoriedad, la prueba puede considerarse como una cadena de tamaño logarítmico fijo. Una máquina de tiempo polinomial podría probar todas las posibles pruebas de tamaño logarítmico 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 verificador).

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

• PCP [ O (log n ), O (1)] = NP (el teorema PCP)
• PCP [poli( n ), O (1)] = PCP [poli( n ),poli( 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 , 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.${\displaystyle \pi \in \mathbb {F} ^{n}}$${\displaystyle q\in \mathbb {F} ^{n}}$${\displaystyle f(q,\pi )}$

• Prueba holográfica en la Enciclopedia de Matemáticas
• Notas del curso de PCP por Subhash Khot en la Universidad de Nueva York , 2008.
• Notas 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