Un enigma matemático capaz de destruir la seguridad mundial

Hay muchas formas de definir qué es ciencia, pero sin duda una de mis favoritas es la de mi compañero y sin embargo amigo, Alberto Márquez. Según él, ciencia es todo aquello que tiene capacidad para destruir el mundo o la especie humana. A continuación, Alberto recuerda que la física ya lo demostró, por ejemplo, en Hiroshima, la química hace poco en Siria, la biología nos regaló las esporas de Bacillus Anthracis...pero, ¿y las matemáticas? ¿Son una ciencia?

No faltan voces que afirman que no, que las matemáticas son solo el lenguaje en el que se escribe la ciencia. Sin embargo, sin embargo, existe un resultado matemático que, de resolverse podría destruir el mundo, al menos, tal y como lo conocemos.

Se trata de uno de esos problemas por cuya resolución el Instituto Clay está dispuesto a pagar un millón de dólares. Ya hablamos de uno de esos problemas, las ecuaciones de Navier-Stokes, y de las importantes consecuencias que su resolución tendría, por ejemplo, en la Fórmula 1. Pero no, no creo que la revolución de la aerodinámica que supondría este avance fuera suficiente para destruir nuestro mundo.

El problema del milenio al que me refiero es otro: ¿es P = NP?

No es fácil describir este problema de forma que lo puedan entender personas ajenas al mundo de la computación, pero trataré de hacerlo en pocas palabras.

¿Qué significa que P sea igual a NP? Si para un problema concreto es fácil comprobar que una solución a dicho problema es correcta (eso sería que el problema es NP), significa eso que el problema es fácil de resolver (eso sería que el problema es P).

Pues, bien, el problema del mensajero, o problema del viajante, conocido como TSP por sus siglas en inglés (travelling salesman problem), es uno de estos problemas NP.

También hablamos de este problema en esta casa, cuando explicamos la necesidad de no dar en consejos a nadie en pro de la evolución de la especie, pero vamos a recordarlo: el problema del mensajero o del viajante consiste en, dado un conjunto de ciudades conectadas por carreteras, diseñar la ruta más corta que, saliendo desde un determinado punto, recorra todas las ciudades y vuelva a dicho punto de partida.

Ya explicamos entonces que, aunque parezca un problema sencillo, no hay forma de resolverlo de manera eficiente ni con todos los ordenadores del mundo, porque es NP. Pero, ¿qué pasa? ¿Que si resolvemos de forma óptima el problema del viajante se destruye el mundo? ¿Se me ha ido la olla o qué?

No, si se demostrase que P=NP, los mensajeros estarían eufóricos y contentos porque se habría mejorado su trabajo. El peligro estaría en que si se demuestra que P=NP también sería muy rápido y fácil de destruir el sistema de criptografía que sirve para cifrar nuestras comunicaciones y, también, claro, las de la NSA, por poner un ejemplo.

Sí, aquellos números primos enormes que le sirvieron a Snowden para poder revelar al mundo que la agencia de espionaje norteamericana se dedicaba a espiar ya no servirían porque sería posible factorizar cualquier número en poco tiempo y, con ello, se acabaría también toda la seguridad actualmente basada en sistemas como el RSA.

Sobre este tema y sobre el peligro real que supondría el hecho de que alguien demostrase que P es igual a NP se ha hizo una película en 2012, 'Travelling Salesman', (El viajante), en la que cuatro matemáticos creen haber conseguido la demostración y se plantean el alcance de su descubrimiento, que si bien sería un avance en la cura de enfermedades, también pone en riesgo la seguridad nacional de cualquier país.

Les dejo el tráiler de la misma en el que nos spoilean que la resolución del travelling salesman problem simplificaría, por ejemplo, el control del tiempo, del poder, de la tecnología, de la política, del dinero, de la energía, de la ciencia, de los datos... de la muerte, de la destrucción, de la aniquilación, de todo. Es una ficción, evidentemente, pero, como dicen en la propia página de la película, las matemáticas son reales. Y las implicaciones también.

Aún no se ha demostrado ni que P=NP ni lo contrario, que P sea distinto de NP. Hay un millón de dólares esperando para el que lo haga pero, como le digo a mis estudiantes, si demuestran que P es distinto de NP, vayan al Instituto Clay a reclamar su millón de dólares (o no, si se sienten un poco Perelman), pero si demuestran que P= NP, destruyan las pruebas, porque siempre será más barato que envíen un sicario a quitarlo a usted de escena que volver a replantearse las comunicaciones y la seguridad mundial.