En la teoría de la complejidad computacional , el teorema de PCP (también conocido como el teorema de caracterización de PCP ) establece que cada problema de decisión en la clase de complejidad NP tiene pruebas probabilísticamente verificables ( pruebas que pueden verificarse mediante un algoritmo aleatorizado ) de complejidad de consulta constante y complejidad de aleatoriedad logarítmica. (utiliza un número logarítmico de bits aleatorios).
El teorema de PCP dice que para alguna constante universal K , para cada n , cualquier prueba matemática de longitud n puede reescribirse como una prueba diferente de longitud poly ( n ) que es formalmente verificable con 99% de precisión mediante un algoritmo aleatorio que inspecciona solo K cartas de esa prueba.
El teorema de PCP es la piedra angular de la teoría de la dureza computacional de la aproximación , que investiga la dificultad inherente en el diseño de algoritmos de aproximación eficientes para varios problemas de optimización . Ingo Wegener lo ha descrito 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 secuencia de obras impresionantes [...] ricas en ideas innovadoras". [2]
Declaración formal
El teorema de PCP establece que
PCP y dureza de aproximación
Una formulación alternativa del teorema de PCP establece que la fracción máxima de restricciones satisfactorias de un problema de satisfacción de restricciones es NP-difícil de aproximar dentro de algún factor constante.
Formalmente, para algunas constantes K y α <1, el siguiente problema de promesa ( L sí , L no ) es un problema de decisión NP-difícil:
- L sí = {Φ: todas las restricciones en Φ se pueden satisfacer simultáneamente}
- L no = {Φ: cada asignación satisface menos de una fracción α de las restricciones de Φ},
donde Φ es un problema de satisfacción de restricciones sobre el alfabeto booleano con como máximo K variables por restricción.
Como consecuencia de este teorema, se puede demostrar que las soluciones a muchos problemas de optimización natural, incluida la capacidad de satisfacción máxima de la fórmula booleana , el conjunto máximo independiente en los gráficos y el problema del vector más corto para las redes , no se pueden aproximar de manera eficiente a menos que P = NP . Estos resultados a veces también se denominan teoremas de PCP porque pueden verse como pruebas probabilísticamente verificables para NP con alguna estructura adicional.
Prueba
Una prueba de un resultado más débil, NP = PCP [n 3 , 1] se da en una de las conferencias de Dexter Kozen. [3]
Historia
El teorema de PCP es la culminación de una larga línea de trabajo sobre demostraciones interactivas y comprobables probabilísticamente. El primer teorema que relaciona demostraciones estándar y demostraciones probabilísticamente comprobables es la afirmación de que NEXP ⊆ PCP [poli ( n ), poli ( n )], demostrado por Babai, Fortnow y Lund (1990) .
Etimología del nombre "teorema de PCP"
La notación PCP c ( n ), s ( n ) [ r ( n ), q ( n )] se explica en Prueba probabilísticamente verificable . La notación es la de una función que devuelve una cierta clase de complejidad. Vea la explicación mencionada anteriormente.
El nombre de este teorema (el "teorema PCP") probablemente proviene de "PCP" que significa " prueba probabilísticamente verificable ", o de la notación mencionada anteriormente (o ambas).
Historia después del primer teorema [en 1990]
Posteriormente, los métodos utilizados en este trabajo fueron ampliados por Babai, Lance Fortnow , Levin y Szegedy en 1991 ( Babai et al. 1991 ), Feige, Goldwasser, Lund, Safra y Szegedy (1991) y Arora y Safra en 1992. ( Arora & Safra 1992 ) para producir una prueba del teorema de PCP por Arora, Lund, Motwani, Sudan y Szegedy en 1998 ( Arora et al. 1998 ).
El Premio Gödel 2001 fue otorgado a Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Carsten Lund , László Lovász , Rajeev Motwani , Shmuel Safra , Madhu Sudan y Mario Szegedy por su trabajo en el teorema PCP y su conexión con la dureza de aproximación.
En 2005, Irit Dinur descubrió una prueba significativamente más simple del teorema de PCP, utilizando gráficos expansores . [4] Recibió el Premio Gödel 2019 por esto. [5]
Análogo cuántico del teorema de PCP
En 2012, Thomas Vidick y Tsuyoshi Ito publicaron un resultado [6] que mostraba una "fuerte limitación en la capacidad de los probadores enredados para coludir en un juego multijugador". Esto podría ser un paso hacia la demostración del análogo cuántico del teorema del PCP, ya que cuando el resultado [6] se informó en los medios, [7] [8] la profesora Dorit Aharonov lo llamó "el análogo cuántico de un artículo anterior sobre multiprover interactivo pruebas "que" básicamente llevaron al teorema de la PCP ". [8]
En 2018, Thomas Vidick y Anand Natarajan demostraron [9] una variante de juegos del teorema cuántico de PCP bajo reducción aleatoria. Establece que QMA ⊆ MIP * [log ( n ), 1,1 / 2], donde MIP * [f (n), c, s] es una clase de complejidad de sistemas de pruebas interactivas cuánticas de múltiples probadores con f ( n ) -bit comunicaciones clásicas, y la integridad es cy la solidez es s. También mostraron que la versión hamiltoniana de una conjetura cuántica de PCP, es decir, un problema hamiltoniano local con brecha de promesa constante c - s es QMA - duro, implica el teorema cuántico de PCP de los juegos.
Notas
- ^ Ingo Wegener (2005). Teoría de la complejidad: exploración de los límites de los algoritmos eficientes . Saltador. pag. 161. ISBN 978-3-540-21045-0.
- ^ Oded Goldreich (2008). Complejidad computacional: una perspectiva conceptual . Prensa de la Universidad de Cambridge. pag. 405. ISBN 978-0-521-88473-0.
- ^ Kozen, Dexter C. (2006). Teoría de la Computación . Textos en Informática. Londres: Springer-Verlag. págs. 119-127. ISBN 9781846282973.
- ^ Consulte la preimpresión de 2005, ECCC TR05-046 . La versión autorizada del artículo es Dinur (2007) .
- ↑ EATSC 2019 Gödel Prize , consultado el 11 de septiembre de 2019 .
- ^ a b Ito, Tsuyoshi; Vidick, Thomas (2012). "Una prueba interactiva de múltiples probadores para el sonido NEXP contra probadores enredados". arXiv : 1207,0550 [ quant-ph ].
- ^ Hardesty, Larry (30 de julio de 2012). "Comunicado de prensa del MIT: problema de 10 años en la informática teórica cae" . Oficina de noticias del MIT. Archivado desde el original el 2 de febrero de 2014 . Consultado el 10 de agosto de 2012 .
Las pruebas interactivas son la base de los sistemas criptográficos que ahora se utilizan ampliamente, pero para los científicos informáticos, son igualmente importantes por la información que brindan sobre la complejidad de los problemas computacionales.
- ^ a b Hardesty, Larry (31 de julio de 2012). "Cae el problema de 10 años en informática teórica" . Oficina de noticias del MIT. Archivado desde el original el 1 de agosto de 2012 . Consultado el 10 de agosto de 2012 .
Dorit Aharonov, profesora de ciencias de la computación e ingeniería en la Universidad Hebrea de Jerusalén, dice que el artículo de Vidick e Ito es el análogo cuántico de un artículo anterior sobre pruebas interactivas multiprover que “básicamente condujo al teorema de PCP, y el teorema de PCP es sin duda el resultado de complejidad más importante de los últimos 20 años ". De manera similar, dice, el nuevo artículo "podría ser un paso importante hacia la demostración del análogo cuántico del teorema de la PCP, que es una cuestión abierta importante en la teoría de la complejidad cuántica".
- ^ Natarajan, A .; Vidick, T. (octubre de 2018). "Pruebas de bajo grado para estados cuánticos y un PCP de juegos enredados cuánticos para QMA". 59º Simposio Anual de IEEE 2018 sobre Fundamentos de las Ciencias de la Computación (FOCS) : 731–742. arXiv : 1801.03821 . Código bibliográfico : 2018arXiv180103821N . doi : 10.1109 / FOCS.2018.00075 . ISBN 978-1-5386-4230-6.
Referencias
- 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.
- Arora, Sanjeev ; Safra, Shmuel (1992), "Approximating clique is NP-complete", En Actas del 33 ° Simposio IEEE sobre Fundamentos en Ciencias de la Computación , 41 (1): 2-13
- 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 ; Levin, Leonid ; Szegedy, Mario (1991), "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, págs. 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º Simposio anual sobre los fundamentos de la informática , IEEE Computer Society, págs. 16-25, ISBN 978-0-8186-2082-9.
- Dinur, Irit (2007), "El teorema de PCP por amplificación de brecha", Journal of the ACM , 54 (3): 12 – es, doi : 10.1145 / 1236457.1236459.
- Feige, Uriel ; Goldwasser, Shafi ; Lovász, László ; Safra, Shmuel ; Szegedy, Mario (1996), "Pruebas interactivas y la dureza de las camarillas aproximadas" (PDF) , Journal of the ACM , ACM, 43 (2): 268-292, doi : 10.1145 / 226643.226652 , ISSN 0004-5411.