Igualdad de clases P y NP

La cuestión de la igualdad de las clases de complejidad P y NP (también conocida en fuentes rusas como problema de enumeración [1] [2] ) ha sido uno de los problemas centrales abiertos en la teoría de algoritmos durante más de tres décadas. Si se le da una respuesta afirmativa, esto significará que es teóricamente posible resolver muchos problemas complejos mucho más rápido que ahora.

La relación entre las clases P y NP se trata en una rama de la teoría de algoritmos denominada teoría de la complejidad computacional . Estudia los recursos necesarios para resolver algún problema. Los recursos más comunes son el tiempo (cuántos pasos dar) y la memoria (cuánta memoria se necesita para completar una tarea).

El problema de la igualdad de las clases P y NP es uno de los siete Problemas del Milenio por los que el Clay Mathematical Institute otorgó un premio de un millón de dólares estadounidenses .

Redacción

En términos generales, el problema de igualdad P = NP es el siguiente: si una respuesta positiva a alguna pregunta se puede verificar con bastante rapidez (en tiempo polinomial ), entonces es cierto que la respuesta a esta pregunta se puede encontrar con bastante rapidez (también en tiempo polinomial ). tiempo y usando memoria polinomial )? En otras palabras, ¿no es realmente más fácil comprobar la solución del problema que encontrarla? [3]

Por ejemplo, ¿es cierto que entre los números { −2 , −3 , 15 , 14 , 7 , −10 , …} hay tales que su suma es igual a 0 ( problema de suma de subconjuntos )? La respuesta es sí , porque −2 −3 + 15 −10 = 0 se verifica fácilmente con algunas adiciones (la información necesaria para verificar una respuesta positiva se llama certificado ). ¿Se deduce que es igual de fácil recoger estos números? ¿Comprobar un certificado es tan fácil como encontrarlo? Parece que sacar números es más difícil, pero esto no ha sido probado.

De la definición de las clases P y NP se sigue inmediatamente el corolario: . Sin embargo, nada se sabe hasta el momento sobre el rigor de esta inclusión, es decir, si existe un problema que radica en NP pero no en P. Si tal problema no existe, entonces todos los problemas pertenecientes a la clase NP se pueden resolver en tiempo polinomial, lo que promete un gran beneficio en la velocidad computacional. Ahora los problemas más complejos de la clase NP (los llamados NP - problemas completos ) se pueden resolver en tiempo exponencial, lo que se considera inaceptable desde un punto de vista práctico.

Historia

La cuestión de la complejidad computacional probablemente fue planteada por primera vez por Kurt Gödel en 1956 en una carta a John von Neumann , donde preguntaba si un problema (ahora conocido como NP-completo) podría resolverse en tiempo cuadrático o lineal . Al mismo tiempo, Gödel sugirió que si existe una solución, esto permitirá que las computadoras resuelvan muchos problemas matemáticos [4] .

La cuestión de la igualdad de clases fue planteada por primera vez por Stephen Cook en 1971 [5] e, independientemente, por Leonid Levin en 1973 [6] .

A principios de la década de 2000 la mayoría de los matemáticos creen que estas clases no son iguales. Según una encuesta realizada en 2002 entre 100 científicos, [7] 61 personas creen que la respuesta es "no igual", 9 - "igual", a 22 les resultó difícil responder y 8 creen que la hipótesis no es derivable de la actual. sistema de axiomas y, por lo tanto, no puede ser probado o refutado.

Al igual que otros problemas matemáticos no resueltos bien conocidos, los intentos de resolver este problema implican un esfuerzo considerable; las pruebas erróneas de la igualdad o desigualdad de las clases P y NP se publican regularmente (no en la literatura científica), generalmente por no profesionales [8] .

Sistemas de protección que asumen la desigualdad de las clases P y NP

Cualquier criptosistema de clave pública se basa en la suposición de la existencia de funciones unidireccionales y/o la duración extrema de la resolución de un determinado problema (por ejemplo, para el algoritmo RSA , esta es la factorización de números muy grandes).

Para proteger los sistemas informáticos del abuso de los servicios, se le pide a la parte solicitante que resuelva un problema que requiere mucho tiempo para encontrar una solución, y la parte que presta el servicio verifica fácil y rápidamente el resultado. Un ejemplo de este tipo de protección antispam es el sistema Hashcash [9] , que utiliza un hash de inversión parcial al enviar correo electrónico.

Las cadenas de bloques basadas en tecnología de prueba de trabajo requieren que la suma de hash resultante sea menor que el valor objetivo. El proceso de búsqueda de la suma hash deseada requiere su recálculo repetido con enumeración de valores arbitrarios del parámetro adicional (para más detalles, consulte Minería ). Todas las computadoras en el sistema pasan una cantidad significativa de tiempo buscando una suma de hash satisfactoria (por ejemplo, en Bitcoin , esto es un promedio de 10 minutos para cada uno de los mineros ). Para verificar la corrección de un bloque ya formado, solo se requiere un único cálculo hash.

Cuestiones similares

• Un problema similar existe en la teoría de la complejidad algebraica para las clases VP y VNP [10] . Por el momento este problema no ha sido resuelto.

• En 2020 se obtuvo una prueba de igualdad de clases de REy MIP* [11] [12] .

Véase también

• fuerza bruta
• problemas matematicos abiertos

Notas

1. ↑ A. A. Razborov. P ?= NP o el problema de la enumeración: una mirada desde los años 90 .
2. ↑ A. H. Shen . El problema de la enumeración  // PostNauka .
3. ↑ Stuart, 2015 , pág. 291.
4. ↑ Hartmanis, Juris. Gödel, von Neumann y el problema P = NP  (neopr.)  // Bulletin of the European Association for Theoretical Computer Science. - T. 38 . - S. 101-107 .
5. ↑ Stephen Cook. La importancia de la pregunta P versus NP Archivado el 9 de julio de 2011 en Wayback Machine .
6. ↑ L. A. Levin. Problemas de enumeración universal  // Problemas de transmisión de información. - 1973. - T. 9 , N º 3 . - S. 115-116 . (Ruso)
7. ↑ Guillermo I. Gasarch. La encuesta P=?NP  (neopr.)  // SIGACT News. - 2002. - T. 33 , N º 2 . - S. 34-47 . -doi : 10.1145/ 1052796.1052804 .
8. ↑ Lenta.ru - Pasado. Los matemáticos finalmente perdieron la fe en resolver el problema del milenio . Consultado el 26 de agosto de 2010. Archivado desde el original el 30 de agosto de 2010. (indefinido)
9. ↑ Hashcash - Una contramedida de denegación de servicio (2002)
10. ↑ Razborov, 2016 , pág. 24
11. ↑ MIP* = RE: prueba histórica de informática que provocó un efecto dominó en física y matemáticas/RUVDS.com Blog/Sudo Null IT News . Consultado el 24 de diciembre de 2020. Archivado desde el original el 12 de mayo de 2021. (indefinido)
12. ↑ [https://web.archive.org/web/20210119084755/https://arxiv.org/abs/2001.04383 Archivado el 19 de enero de 2021 en Wayback Machine [2001.04383] MIP*=RE]

Literatura

• Ian Stewart . Los mejores problemas de matemáticas. — M. : Alpina no ficción, 2015. — 460 p. - ISBN 978-5-91671-318-3 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M. : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .
• Razborov A. A. Complejidad algebraica. — M .: MTsNMO , 2016. — 32 p. - ISBN 978-5-4439-1032-1 .

Enlaces

• S. Cook Descripción oficial del problema  (ing.)
• S. Nikolenko "P=?NP" . Computerra, 2006.
• N. P. Varnovsky. Problema P=? NP, clases de complejidad y criptografía . 2005.
• Pritykin Yu. L. ¿Cuál es el problema de P vs. ¿NOTARIO PÚBLICO?  // VIII Escuela de Verano "Matemáticas Modernas". — Dubná, 2008.
• Gerhard J. Woeginger. La página P-versus-NP . (ing.) Lista de enlaces a "soluciones" propuestas a este problema hasta 2016. Algunos de ellos afirman la igualdad de P y NP , algunos, lo contrario.
• Scott Aaronson. Razones para creer que P!=NP
• Scott Aaronson . — Revisión de 2017.

diccionarios y enciclopedias	Britannica (en línea) Britannica (en línea)