En la teoría de la complejidad computacional , una prueba probabilísticamente verificable ( 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. A continuación, se requiere que el algoritmo acepte pruebas correctas y rechace pruebas incorrectas con una probabilidad muy alta. Una prueba (o certificado ) estándar , como se utiliza en la definición basada en el verificador de la clase de complejidad NP, 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 incorrectas. Sin embargo, lo que los hace interesantes es la existencia de pruebas probabilísticamente verificables que se pueden verificar leyendo solo unos pocos fragmentos de la prueba usando la aleatoriedad de una manera esencial.
Las pruebas probabilísticamente verificables 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 demostraciones probabilísticamente comprobables que se pueden verificar 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, las pruebas correctas siempre deben aceptarse 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 .
Definición
Dado un problema de decisión L (o una lengua L con su conjunto alfabético Σ), un sistema de prueba probabilísticamente verificable 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 probador produce una prueba π que establece que x resuelve L ( x ∈ L , la prueba es una cadena ∈ Σ * ). Y el verificador es un oráculo aleatorio Turing Machine V (el verificador ) que verifica la prueba π para el enunciado de que x resuelve L ( ox ∈ L ) y decide si acepta el enunciado. El sistema tiene las siguientes propiedades:
- Completitud : Para cualquier x ∈ L , dada la prueba π producida por el comprobador del sistema, el verificador acepta la declaración con una probabilidad de al menos c ( n ),
- Solidez : Para cualquier x ∉ L , luego para cualquier prueba π , el verificador acepta erróneamente la declaració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 la 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 extensión de la prueba, ya que generalmente incluye el alfabeto y todos los testigos. Para el prover, no nos importa cómo se llega a la solución del problema; solo nos importa la prueba que da de la membresía de la solución en el idioma.
Se dice que el verificador no es adaptable 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 probabilísticamente verificables sobre el alfabeto binario de integridad 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, ½ [ r ( n ), q ( n )]. La clase de complejidad PCP se define como PCP 1, ½ [O (log n ), O (1)].
Historia y significado
La teoría de pruebas probabilísticamente verificables estudia el poder de los sistemas de prueba probabilísticamente verificables bajo varias 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 explícitamente introducida 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 probabilísticamente verificables. [3] El teorema de PCP probado 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 probabilísticamente verificables.
Propiedades
Desde el punto de vista de la complejidad computacional, para configuraciones extremas de los parámetros, la definición de pruebas probabilísticamente verificables se considera 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 para no tener aleatoriedad ni 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 del tiempo polinomial podría probar todas las pruebas de tamaño logarítmico posibles en tiempo polinomial).
- PCP [poli ( n ), 0] = coRP (Por definición de coRP .)
- PCP [0, poli ( n )] = NP (según la definición de NP basada en el verificador).
El teorema de PCP y MIP = NEXP se pueden caracterizar de la siguiente manera:
- PCP [O (log n ), O (1)] = NP (el teorema de 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 , poli ( n )] = NP . Por otro lado, si NP ⊆ PCP [o (log n ), o (log n )] entonces P = NP . [2]
PCP lineal
El PCP lineal es uno tal que dada la consulta q, el oráculo solo realiza una operación lineal en la prueba . Es decir, la respuesta del oráculo a la consulta q es una función lineal.
Ver también
Referencias
- ^ Arora, Sanjeev ; Barak, Boaz (2007), Computational Complexity: A Modern Approach , Cambridge University Press , pág. 241, ISBN 978-0-521-42426-4
- ^ a b c Arora, Sanjeev ; Safra, Shmuel (1998), "Comprobación probabilística de pruebas: una nueva caracterización de NP", Journal of the ACM , 45 (1): 70-122, doi : 10.1145 / 273865.273901
- ^ Babai, László ; Fortnow, Lance ; Lund, Carsten (1990), "El tiempo exponencial no determinista tiene protocolos interactivos de dos probadores", Actas del 31 ° Simposio anual sobre fundamentos de la informática (FOCS 1990) , págs. 16-25, CiteSeerX 10.1.1.130.9311 , doi : 10.1109 / FSCS.1990.89520 , ISBN 978-0-8186-2082-9
- ^ Arora, Sanjeev ; Lund, Carsten ; Motwani, Rajeev ; Sudán, Madhu ; Szegedy, Mario (1998), "Verificación de la prueba y la dureza de los problemas de aproximación", Journal of the ACM , 45 (3): 501–555, doi : 10.1145 / 278298.278306
enlaces externos
- Prueba holográfica .
- Subhash Khot . Notas del curso de PCP . Universidad de Nueva York, 2008.
- Ryan O'Donnell y Venkatesan Guruswami. Notas del curso de PCP y una historia del teorema de PCP . Universidad de Washington, 2005.
- Complejidad Zoo : PCP