Teorema PCP

En la teoría de la complejidad computacional , el teorema PCP (también conocido como teorema de caracterización PCP ) establece que todo problema de decisión en la clase de complejidad NP tiene pruebas verificables probabilísticamente ( pruebas que pueden ser verificadas por un algoritmo aleatorio ) de complejidad de consulta constante y complejidad de aleatoriedad logarítmica (utiliza un número logarítmico de bits aleatorios).

El teorema PCP dice que para alguna constante universal${\displaystyle K}$, por cada${\displaystyle n}$cualquier prueba matemática para una afirmación de longitud${\displaystyle n}$puede reescribirse como una prueba de longitud diferente${\displaystyle \operatorname {poly} (n)}$que es formalmente verificable con un 99% de precisión mediante un algoritmo aleatorio que inspecciona únicamente${\displaystyle K}$cartas de esa prueba.

El teorema PCP es la piedra angular de la teoría de la dificultad computacional de la aproximación , que investiga la dificultad inherente al diseño de algoritmos de aproximación eficientes para diversos problemas de optimización . Ingo Wegener lo describió como «el resultado más importante en la teoría de la complejidad desde el teorema de Cook » ^{[ 1 ]} y Oded Goldreich como «la culminación de una serie de trabajos impresionantes […] ricos en ideas innovadoras» ^{[ 2 ] .}

El teorema PCP establece que$${\displaystyle {\mathsf {NP}}={\mathsf {PCP}}[O(\log n),O(1)]}$$ dónde${\displaystyle {\mathsf {NP}}}$es la clase de complejidad de problemas resolubles en tiempo polinomial no determinista y donde${\displaystyle {\mathsf {PCP}}[r(n),q(n)]}$es la clase de problemas para los cuales se puede dar una prueba verificable probabilísticamente de una solución, de tal manera que la prueba se puede verificar en tiempo polinomial utilizando${\displaystyle r(n)}$fragmentos aleatorios y leyendo${\displaystyle q(n)}$fragmentos de la prueba, las pruebas correctas siempre se aceptan y las pruebas incorrectas se rechazan con una probabilidad de al menos${\displaystyle {\tfrac {1}{2}}}$. La variable${\displaystyle n}$es la longitud en bits de la descripción de una instancia del problema. Cabe destacar además que el algoritmo de verificación no es adaptativo : la selección de bits de la prueba a comprobar depende únicamente de los bits aleatorios y de la descripción de la instancia del problema, no de los bits reales de la prueba.

Una formulación alternativa del teorema PCP establece que la fracción máxima de restricciones satisfacibles de un cierto problema de satisfacción de restricciones es NP-difícil de aproximar dentro de algún factor constante. ^{[ 3 ]}

Formalmente, para algunas constantes${\displaystyle q}$y${\displaystyle \alpha <1}$, el siguiente problema de promesa${\displaystyle (L_{\mathrm {sí} },L_{\mathrm {no} })}$es un problema de decisión NP-difícil:

• ${\displaystyle L_{\mathrm {sí} }=\{\Phi$ :} todas las restricciones en${\displaystyle \Phi }$son simultáneamente satisfacibles${\displaystyle \}}$
• ${\displaystyle L_{\mathrm {no} }=\{\Fi$ :} cada asignación satisface menos de un${\displaystyle \alpha }$fracción de${\displaystyle \Phi }$restricciones${\displaystyle \}}$

dónde${\displaystyle \Phi }$es un problema de satisfacción de restricciones (CSP) sobre un alfabeto booleano con como máximo${\displaystyle q}$variables por restricción.

La conexión con la clase${\displaystyle {\mathsf {PCP}}}$Lo mencionado anteriormente se puede observar al comprobar un número constante de bits.${\displaystyle q}$en una demostración se puede ver como evaluar una restricción en${\displaystyle q}$Variables booleanas en esos bits de la prueba. Dado que el algoritmo de verificación utiliza${\displaystyle O(\log n)}$bits aleatorios, se puede representar como un CSP como se describió anteriormente con${\displaystyle \operatorname {poly} (n)}$restricciones. La primera formulación del teorema PCP garantiza entonces la condición de promesa con${\displaystyle \alpha ={\tfrac {1}{2}}}$: si la respuesta al problema NP es sí, entonces cada restricción (que corresponde a un valor particular para los bits aleatorios) tiene una asignación satisfactoria (una prueba aceptable); de lo contrario, cualquier prueba debe ser rechazada con una probabilidad de al menos${\displaystyle {\tfrac {1}{2}}}$, lo que significa que cualquier asignación debe satisfacer menos de${\displaystyle {\tfrac {1}{2}}}$de las restricciones (lo que significa que será aceptado con una probabilidad menor que${\displaystyle {\tfrac {1}{2}}}$Por lo tanto, un algoritmo para el problema de la promesa sería capaz de resolver el problema NP subyacente, y por consiguiente el problema de la promesa debe ser NP-difícil.

Como consecuencia de este teorema, se puede demostrar que las soluciones a muchos problemas de optimización natural, incluyendo la satisfacibilidad máxima de fórmulas booleanas , ^{[ 4 ]} el conjunto independiente máximo en grafos, ^{[ 5 ]} y el problema del vector más corto para retículos ^{[ 6 ]} no pueden aproximarse eficientemente a menos que${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$Esto se puede lograr reduciendo el problema de aproximar una solución a dichos problemas a un problema de promesa de la forma descrita anteriormente. Estos resultados también se denominan a veces teoremas PCP, ya que pueden considerarse pruebas verificables probabilísticamente para NP con alguna estructura adicional.

Una demostración de un resultado más débil ,${\displaystyle {\mathsf {NP}}\subseteq {\mathsf {PCP}}[n^{3},1]}$Se da en una de las conferencias de Dexter Kozen. ^{[ 7 ]}

El teorema PCP es la culminación de una larga línea de trabajo sobre demostraciones interactivas y demostraciones verificables probabilísticamente. El primer teorema que relaciona las demostraciones estándar y las demostraciones verificables probabilísticamente es la afirmación de que${\displaystyle {\mathsf {NEXP}}\subseteq {\mathsf {PCP}}[\operatorname {poly} (n),\operatorname {poly} (n)]}$, demostrado por Babai, Fortnow y Lund (1990) .

• Arora, Sanjeev ; Lund, Carsten ; Motwani, Rajeev ; Sudán, Madhu ; Szegedy, Mario (1998), "Verificación de pruebas y dureza de los problemas de aproximación", Journal of the ACM , 45 (3): 501– 555, doi : 10.1145/278298.278306 , S2CID 8561542 .
• Arora, Sanjeev ; Safra, Shmuel (1992), "Aproximar clique es NP-completo", En Actas del 33.er Simposio IEEE sobre Fundamentos de la Informática , 41 (1): 2–13
• Arora, Sanjeev ; Safra, Shmuel (1998), "Verificación probabilística de pruebas: una nueva caracterización de NP", Journal of the ACM , 45 (1): 70–122 , doi : 10.1145/273865.273901 , S2CID 751563 .
• Babai, László ; Fortnow, Lance ; Levin, Leonid ; Szegedy, Mario (1991), "Checking computations in polylogarithmic time", STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing , ACM, pp. 21–32 , ISBN  978-0-89791-397-3.
• Babai, László ; Fortnow, Lance ; Lund, Carsten (1990), "El tiempo exponencial no determinista tiene protocolos interactivos de dos probadores", SFCS '90: Actas del 31.er Simposio Anual sobre Fundamentos de la Informática , IEEE Computer Society, págs. 16-25 , ISBN  978-0-8186-2082-9.
• Dinur, Irit (2007), "El teorema PCP por amplificación de espacios", Journal of the ACM , 54 (3): 12–es, doi : 10.1145/1236457.1236459 , S2CID 53244523 .
• Feige, Uriel ; Goldwasser, Shafi ; Lovász, László ; Safra, Shmuel ; Szegedy, Mario (1996), "Pruebas interactivas y la dificultad de aproximar cliques" (PDF) , Journal of the ACM , 43 (2), ACM: 268–292 , doi : 10.1145/226643.226652 , ISSN 0004-5411 , archivado del original (PDF) el 10 de junio de 2011 , recuperado el 24 de mayo de 2010 . .