En este artículo me gustaría centrarme en uno de los problemas del milenio: el problema P vs NP, ya que no solo tiene especial importancia en el campo de las matemáticas, sino que influye directamente en la informática y, para que mentir, en todos nosotros.
Para aquellos que no lo sepáis los 7 problemas del milenio son los siete problemas matemáticos más importantes sin resolver, publicados en el año 2000 por el Instituto Clay de Matemáticas de Cambridge, Estados Unidos (aunque su planteamiento fue anterior).
¿Y por qué la pregunta del millón de dólares?, porque el premio por su resolución son nada más y nada menos que 1.000.000 de dólares, y seguramente en la gran mayoría de los casos, ser galardonado con el más alto honor entre los matemáticos: Medalla Fields. Este premio es el sustituto del Nobel de las Matemáticas, curioso el hecho de que este galardón no exista – las leyendas dicen que es debido a que la amante de Nobel tenía una aventura con un matemático, pero la opción más verosímil es que Nobel no presentaba mucho interés en las mismas -. Volviendo al tema que nos trata, actualmente solo se ha conseguido resolver uno de los 7 problemas: la conjetura de Poincaré. En 2002 el matemático ruso Grigori Perelmán dio con la solución para 3 dimensiones (para n>3 ya se había encontrado una solución), lo que permitió dejar totalmente cerrado el problema.
La resolución de la hipótesis de Poincaré hizo que se le concediera la Medalla Fields anteriormente mencionada, premio que rechazó porque, cito textualmente: “no quería convertirse en una mascota para el mundo de las matemáticas”.
En el año 2018 el británico Michael Atiyah aseguró haber solucionado el problema de la Hipótesis de Riemann al hallar una fórmula con la que predecir el siguiente número primo dentro de una serie de cifras, pero para ser aceptada su teoría debe ser publicada por una revista científica de prestigio mundial. Posteriormente, si la teoría es aceptada por la comunidad matemática, tendrá que recibir el visto bueno de dos comités independientes de expertos del Instituto Clay. Poca cosa como podéis observar.
Comenzamos pues con el tema que nos trajo hasta aquí:
EL PROBLEMA P vs. NP
Este problema no atinge tan solo a los matemáticos, sino que también es muy importante en la comunidad informática, ya que se trata de la clasificación de los problemas según el número de pasos que necesitaría ejecutar el mejor algoritmo conocido para resolverlos.
En teoría de la computación, se citan tres de las clases principales (también existen los problemas intratables, pero en este caso no nos interesan), las cuales no son mutuamente excluyentes:
- PROBLEMAS DE TIPO P: Aquellos cuya solución puede encontrarse con rapidez.
Ejemplo: Dado un mapa de carreteras en el que aparecen
ciudades, ¿es posible ir desde cualquier ciudad hasta cualquier otra? Para un valor elevado de , el número de pasos que necesita ejecutar un ordenador crece como 
; es decir, como un polinomio en .
Dado que el valor de un polinomio aumenta de manera relativamente modesta a medida que lo hace, los ordenadores pueden resolver problemas de tipo P en un tiempo razonable. - PROBLEMAS NP: Aquellos cuya solución puede verificarse con rapidez.
Ejemplo: Supongamos que sabemos que cierto número de dígitos es el producto de dos números primos grandes y que deseamos hallar dichos factores. Si alguien nos los proporciona, podremos comprobar en tiempo polinómico (multiplicándolos) que constituyen la solución. - PROBLEMAS NP-COMPLETOS: No deterministas en tiempo polinómico. Los más difíciles de resolver.
Ejemplo: Dado un mapa con países, ¿será posible pintarlo con solo tres colores de modo que no haya países contiguos del mismo color? Si existiera un algoritmo para resolver este problema en tiempo polinómico, dicho algoritmo podría adaptarse para resolver cualquier otro problema de tipo NP (como el de la descomposición en factores primos).
En este sentido, los problemas NP-completos constituyen los problemas NP de máxima dificultad. Hasta hoy no se conoce ningún algoritmo capaz de resolver de manera eficiente un problema de tipo NP-completo.
¿Cuál es entonces el problema que tiene en jaque a gran parte de los matemáticos e informáticos? Pues el hecho es que se ha conseguido demostrar que si se puede encontrar fácilmente una solución para un problema NP, esta también se podrá verificar de manera sencilla, por lo que todo problema P es también NP. Pero no se ha conseguido demostrar que existan problemas NP que no sean P.
Esto se debe a que este tipo de problemas presentarían soluciones tan a largo plazo que no tenemos el tiempo suficiente para llegar al momento de la solución, ni siquiera con ordenadores cuánticos (estamos hablando de cientos de años computando).
Y, ¿por qué preocupa tanto su resolución? Básicamente porque todos los sistemas de criptografía y seguridad online que existen en la actualidad se basan en problemas del tipo NP y, en caso de demostrar que NP equivale a P, las claves criptográficas se descifrarían con gran facilidad, y muchas cuentas bancarias y comunicaciones cifradas quedarían expuestas a los amigos de lo ajeno.
Esto se debe a que la gran mayoría de los algoritmos de encriptación utilizados en la actualidad se basan en la descomposición en factores de un número (un problema del tipo NP).
Si alguien consiguiese demostrar que P=NP estaríamos ante una crisis a nivel mundial, los sistemas criptográficos quedarían invalidados y se marcaría una etapa sin precedentes en la historia.
¿Y qué pasaría si se descubre que P≠NP? En este caso las consecuencias no serían muchas. Básicamente dejaríamos de buscar algoritmos polinomiales para una serie de problemas, porque sabríamos con seguridad que tales algoritmos no existen, es decir, no podríamos expresar los problemas NP como P.
En dicho caso… ¿existiría otra forma de resolver los problemas NP? 🤔
A continuación os adjunto un vídeo en el cual se explica muy bien el problema.
Si te ha gustado este artículo y quieres que explique algún otro problema del milenio házmelo saber en los comentarios 😉.
AUTORA
María Caseiro Arias
Estudiante de Matemáticas e Ing.Informática
Santiago de Compostela
BIBLIOGRAFÍA
María Caseiro Arias
Coordinadora de desarrollo y diseño web de QS.
Estudiante de 6º de Matemáticas e Ing.Informática en la Universidad de Santiago de Compostela.
3 Respuestas
Resolver un problema que basicamente nos costaria la economia global
Sería un momento crítico en la economía mundial exactamente, habría que cambiarlo todo. La cuestión es, merece la pena?
[…] la factorización de números primos de gran magnitud (como mencionamos con anterioridad en el artículo de P=NP), pero resulta teóricamente posible tirar abajo cualquier barrera de este […]