Teorema de PCP
En la teoría de la complejidad computacional , el teorema PCP ( pruebas comprobables probabilísticamente - prueba verificable probabilísticamente) establece que cualquier solución a un problema de decisión en la clase de complejidad NP tiene una prueba verificable probabilísticamente (una prueba que se puede verificar usando un algoritmo aleatorio ) de complejidad de consulta constante y complejidad logarítmica de aleatoriedad (utiliza un número logarítmico de bits aleatorios).
El teorema PCP es la piedra angular de la teoría de la complejidad computacional de aproximación , que explora la complejidad inherente en el desarrollo de algoritmos de aproximación eficientes para diversos problemas de optimización . El teorema es señalado por Ingo Wegener como "el resultado más importante en la teoría de la complejidad desde el teorema de Cook " [1] y por Oded Goldreich como "la culminación de una cadena de trabajos impresionantes […] ricos en nuevas ideas " [2] .
También hay críticas. Entonces, en el libro de Boss [3] se dice: “En un momento causó sensación. La bola de nieve de publicaciones sigue creciendo... La nueva definición, en esencia, de la clase NP arroja luz adicional, pero sin muchas consecuencias. … En cuanto al sistema PCP en sí, se basa esencialmente en el Oráculo mágico y, por lo tanto, no libera la igualdad NP = PCP [O(log n ), O(1)] en el plano práctico”.
El teorema de PCP establece que
NP = PCP [O(log n ), O(1)] [3] [4] .PCP y complejidad de aproximación
Una formulación alternativa del teorema PCP establece que la búsqueda de la máxima proporción de condiciones satisfechas en el problema de restricción es NP-difícil de aproximar con un coeficiente constante.
Formalmente, para alguna constante K y α < 1, el problema ( L sí , L no ) es un problema de decisión NP-difícil:
- L sí = {Φ: todas las restricciones en Φ son satisfactorias}
- L no = {Φ: bajo cualquier sustitución, la proporción de restricciones satisfechas Φ no excede α }.
Aquí Φ es el problema de satisfacer las condiciones de restricción sobre un alfabeto booleano con como máximo K variables por constante [5]
Como consecuencia de este teorema, se puede demostrar que las soluciones a muchos problemas de optimización, incluida la búsqueda de la máxima satisfacibilidad de las fórmulas booleanas , el máximo conjunto independiente en un gráfico y el vector de red más corto , no se pueden aproximar eficientemente a menos que P = NP está satisfecho .
Estos resultados a veces también se denominan teoremas PCP porque pueden verse como pruebas probabilísticamente verificables de problemas NP con algunas estructuras adicionales.
Historia
El teorema PCP es la culminación de un largo camino en el desarrollo de demostraciones y verificables probabilísticamente.
El primer teorema, que vincula las pruebas ordinarias y las pruebas probabilísticamente verificables, establece que , y se demostró en el libro de 1990 [6] .
![NEXP\subseteq PCP[poli(n),poli(n)]](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2d60d385ba83bf0fba242c2aba82c455ea06db3)
Historia desde la primera prueba del teorema en 1990
Posteriormente, el método utilizado en este artículo fue ampliado en el artículo de Babai, Fortnov, Levin, Shegedi (1991) [7] , así como en los artículos de Feige, Goldwasser, Lund, Shegedi (1991) y Arora y Safra (1992) [8] , que proporcionó una prueba del teorema PCP en un artículo de 1992 de Arora, Lund, Motwani, Sudan y Shegedi [9] . En 2001, el Premio Gödel fue otorgado a Sanjeev Arora , Uriel Feiga , Shafi Goldwasser , Karsten Lund Laszlo Lovas , Rajiv Motwani , Shmuel Safra , Sudan y Szegedi por su trabajo sobre el teorema PCP y su
En 2005, Irit Dinur descubrió otra prueba del teorema PCP utilizando expansores [5] .
Análogo cuántico del teorema PCP
En 2012, Thomas Vidick y Tsuyoshi Ito publicaron un artículo [10] que mostraba "la grave limitación de los controles de colusión complejos en un juego multijugador". Este es un importante paso adelante para probar un análogo cuántico del teorema PCP [11] , y la profesora Dorit Aharonov lo llamó "un análogo cuántico de un artículo anterior sobre pruebas interactivas", que "esencialmente condujo al teorema PCP" [12] .
Notas
- ↑ Ingo Wegener. El tiempo exponencial no determinista tiene protocolos interactivos de dos probadores // Teoría de la complejidad: Explorando los límites de los algoritmos eficientes . - Springer, 2005. - ISBN 978-3-540-21045-0 .
- ↑ Oded Goldreich. Complejidad Computacional: Una Perspectiva Conceptual . - Prensa de la Universidad de Cambridge, 2008. - ISBN 978-0-521-88473-0 . Archivado el 13 de abril de 2014 en Wayback Machine .
- ↑ 1 2 Boss V. Fuerza bruta y algoritmos eficientes: guía de estudio. - M .: Editorial LKI, 2008. - T. 10. - (Conferencias sobre matemáticas). - ISBN 978-5-382-00642-0 .
- ↑ José Falcón, Mitesh Jain. Una introducción a las pruebas comprobables probabilísticamente y al teorema PCP . - 2013. - S. 3 . Archivado desde el original el 14 de febrero de 2019.
- ↑ 1 2 Irit Dinur. El teorema de PCP por amplificación de espacios // Revista de la ACM. - 2007. - T. 54 , núm. 3 . - S. 70-122 . -doi : 10.1145/ 1236457.1236459 .
- ↑ Lászlo Babai, Lance Fortnow, Carsten Lund. El tiempo exponencial no determinista tiene protocolos interactivos de dos probadores // SFCS '90: Actas del 31.er Simposio Anual sobre Fundamentos de Ciencias de la Computación. - IEEE Computer Society, 1990. - S. 16-25. - ISBN 978-0-8186-2082-9 .
- ↑ László Babai, Lance Fortnow, Leonid Levin, Mario Szegedy. Comprobación de cálculos en tiempo polilogarítmico // STOC '91: Actas del vigésimo tercer simposio anual de ACM sobre teoría de la computación. - ACM, 1991. - Págs. 21-32. - ISBN 978-0-89791-397-3 .
- ↑ Sanjeev Arora, Shmuel Safra. Comprobación probabilística de pruebas: Una nueva caracterización de NP // Revista de la ACM. - 1998. - T. 45 , núm. 1 . - S. 70-122 . -doi : 10.1145/ 273865.273901 .
- ↑ Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy. Prueba de verificación y la dureza de los problemas de aproximación // Diario de la ACM. - 1998. - T. 45 , núm. 3 . - S. 501-555 . -doi : 10.1145/ 278298.278306 .
- ↑ Ito, Tsuyoshi; Vidick, Thomas Una prueba interactiva de probadores múltiples para el sonido NEXP contra probadores enredados .
- ↑ Hardesty, Larry Comunicado de prensa del MIT: Falla un problema de 10 años de antigüedad en informática teórica . Oficina de noticias del MIT (30 de julio de 2012). “Los controles interactivos son la base de los sistemas criptográficos y ahora se usan ampliamente, pero para los informáticos son solo un medio importante para penetrar la esencia de los problemas de complejidad computacional”. Consultado el 10 de agosto de 2012. Archivado desde el original el 10 de agosto de 2012.
- ↑ Hardesty, Larry Problema de 10 años en informática teórica cae . Oficina de noticias del MIT (31 de julio de 2012). “Dorit Aharonov, profesora de la Universidad Hebrea de Jerusalén, dijo que el artículo de Vidick e Ito es un análogo cuántico de un artículo anterior sobre pruebas interactivas, que “esencialmente condujo al teorema del PCP, y en sí mismo. El teorema del PCP es sin duda el resultado más importante en la teoría de la complejidad en los últimos 20 años”. También dijo que el nuevo documento "parece ser un importante paso adelante para demostrar el análogo cuántico del teorema PCP, que ahora es la principal pregunta abierta en la teoría de la complejidad de la computación cuántica". Consultado el 10 de agosto de 2012. Archivado desde el original el 9 de agosto de 2012.
Literatura
- Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy. Demostraciones interactivas y la dureza de aproximar camarillas // Diario de la ACM. - 1996. - T. 43 , núm. 2 . - S. 268-292 . -doi : 10.1145/ 226643.226652 .