P=NP: El cartel de cine más geek

Estrenada en 2012, Travelling Salesman es un «thriller intelectual» donde ocurre lo que muchos consideran impensable en ciencias de la computación: un grupo de matemáticos demuestra que P=NP. Como es «lógico», los descubridores se verán ante el dilema de reconocer su hallazgo a pesar de saber que podría cambiar el mundo.

Realmente, la película pretende acercar al público lo mucho que la sociedad moderna depende de la tecnología y, sin que muchos se den cuenta, de matemáticas puras y duras. Un caso bastante bien conocido es la criptografía: cada vez que compramos por Internet, enviamos nuestros datos y número de tarjeta de crédito cifrados a través de decenas de enrutadores y servidores por medio mundo. Sólo gracias a un teorema matemático y la dificultad de realizar una «cuenta difícil» podemos estar tranquilos de que ningún intermediario puede descifrar esa información.

La clave está en que cifrar o descifrar un mensaje es algo sencillo conociendo la clave, pero es muy difícil sin ella. Para los científicos de la computación, forma parte de lo que se llama familia de algoritmos de complejidad P, por tiempo polinómico. Resumiendo mucho, por otro lado encontramos algoritmos con complejidad NP, a los que es extremadamente difícil encontrar una solución pero muy fácil verificar si una solución es válida una vez dada. Por ejemplo, colocar una serie de paquetes en una mochila para que la rellenen completamente, dejando el mínimo de huecos, es extremadamente difícil. Pero si te la dan ya rellena, es trivial verificar que todo está bien empaquetado.

A día de hoy, nadie sabe si los problemas de NP se pueden convertir en problemas de tipo P de alguna manera. Las implicaciones de que sí se pudiera serían enormes, tanto positivas como negativas. Empezando por lo malo, toda la seguridad informática basada en criptografía podría tambalearse (dependiendo del tipo de hallazgo), con lo que eso implicaría en escuchas de teléfonos móviles, comunicaciones por Internet, acceso a datos cifrados, etc.

Aún así, es posible que las supuestas ventajas fueran aún más destructivas: casi todos los algoritmos que frenan el avance de la inteligencia artificial son NP-completos, por lo que todo lo relativo a máquinas que analicen y aprendan del mundo entraría en una edad de oro. Se verían afectados desde el estudio del plegado de proteínas para tratar cáncer hasta el diseño de nuevos métodos de especulación en los mercados financieros o drones de guerra más inteligentes y autónomos.

¿Merecería la pena vivir en un mundo donde P=NP?