158.- El problema del viajante
Es evidente, sin más que ver el cartel anunciador de la película, que esta película contiene algo de matemáticas. Quizá para el público general sólo se lo sugieran los ceros y unos, y por eso pensará seguramente que tiene más que ver con la informática (que también), pero no me digan que ese P = NP, y el propio título, no lo delatan claramente. Por terminar la leyenda: De potestate ideam est virtutem dei, significa “La idea es controlar el poder”.
Ficha Técnica:
Título Original: Travelling Salesman. Nacionalidad:
EE. UU, 2012. Dirección: Timothy
Lanzone. Guion: Andy
Lanzone y Timothy Lanzone. Fotografía:
Benji
Bakshi, en Color. Montaje: Christopher
McGlynn. Música: Benjamin
Krause. Producción: Clay
Reed. Duración: 80 min
Ficha artística:
Intérpretes: Danny Barclay (Nº 1 - Tim Horton), Eric Bloom (Nº 2), David John Cole (Profesor Acuri), Malek Houlihan (Hombre misterioso), Matt Lagan (Nº 4), Marc Raymond (Nº 5), Tyler Seiple (Nº 3), Steve West (Hugh).
Argumento
Muy sencillo. El gobierno norteamericano encarga a cuatro matemáticos la tarea de resolver el problema más potente de la historia de las ciencias de la computación. Con ello tendrán un control y un poder casi absoluto. Tienen éxito, pero uno de ellos se niega a desvelar sus descubrimientos. La película es un debate sobre la moralidad, la pertinencia o no de conocer determinados descubrimientos y el uso que se pueda hacer de ellos dependiendo de la ética del que los posea, etc.
Algunos conceptos y curiosidades
En este caso, hay que reconocer que no es una película demasiado comercial (en realidad, nada comercial), ya que el noventa por ciento de la misma se desarrolla con cuatro o cinco personas hablando y debatiendo en torno a una mesa. Entre las frases que he leído para definirla está la de thriller cerebral, con lo que queda claro que no es sencilla de visualizar.
Destripar cada referencia, cada frase que contiene nos llevaría demasiado espacio, de modo que en esta ocasión les dejo un par de pinceladas sobre las clase de complejidad, y otro par de diálogos en castellano (traducidos a mi manera, porque no hay, que yo sepa, versión doblada, ni siquiera subtitulada, o yo al menos no la he encontrado). Cualquier comentario o aclaración que los lectores nos hagan llegar será, como siempre, bienvenido, y en esta ocasión con más razón.
El problema P vs. NP es el problema sin resolver más trascendente de la informática. Se formuló por primera vez en 1971, y se pregunta si una clase de problemas (NP) es más difícil que otra clase (P). Los matemáticos agrupan los problemas en distintas clases según el tiempo que tardan en resolverse y verificarse. NP es la clase de problemas cuya respuesta se puede verificar (sólo verificar) en un período de tiempo razonable. Algunos problemas NP también se pueden resolver rápidamente, pero no todos. Cuando se pueden resolver (y nos referimos a que una máquina programada mediante un algoritmo determinístico y secuencial lo puede resolver), se dice que esos problemas están en la clase P, cuya letra indica tiempo polinomial en proporción a los datos de entrada. Sin embargo, hay otros problemas en NP que nunca se han resuelto en tiempo polinomial.
Veamos un par de ejemplos rápidos de este tipo de clases de problemas. Sumar dos números enteros de longitud k es un problema P y el tiempo requerido para resolverlo es O(k) (esto quiere decir que es del mismo orden que k). Multiplicar dos números enteros de longitud k y l, con k > l es otro problema P y el tiempo que se necesita para hacerlo es O(k2), con el algoritmo usual de multiplicación (aunque hay algoritmos que permiten hacerlo en tiempo menor). Calcular el máximo común divisor de dos números también es un problema P. Un problema NP es, por ejemplo, dado un número de N cifras, hallar su descomposición en números primos. Entiéndase lo que se está diciendo porque seguro que más de uno piensan que eso es un problema P. No nos referimos a un número de 300 cifras; nos referimos a cualquier número de cualquier longitud. Igual pasa con el célebre problema del viajante: uno puede verificar un caso concreto. Diez ciudades y calcular la menor ruta posible (aunque con diez ya sería un asunto de cierta complejidad, no olvidemos que existen 10! posibilidades (o sea 3628800) de establecer la ruta. Hacerlo con cualquier número de ciudades es un problema NP (además un NP-duro; porque dentro de los NP hay varias subcategorias).
Es evidente que todo problema P es NP (si podemos resolverlo, podemos comprobar si la solución es válida). Lo que no se sabe es si es posible resolver todos los problemas NP tan rápidamente como los problemas P. Algunas preguntas NP parecen más difíciles que las preguntas P, pero puede que no lo sean.
Muchos criptosistemas, que se utilizan para proteger los datos de todo el mundo, se basan en la suposición de que no pueden resolverse en tiempo polinomial. Pero si se demostrara que esto no es así (lo que ocurre en la película, que alguien ha resuelto el enigma), entonces esos sistemas de cifrado serían vulnerables, y se podrían descifrar todos los lugares en los que se hubieran aplicado (y por consiguiente el que lo tuviera tendría acceso a toda la información secreta de todo el mundo, gobiernos, bancos, clientes, todo). Pero no todo sería malo, porque también podrían, citan en uno de los diálogos, realizarse avances muy notables en bioinformática, que salvarán muchas vidas, o química teórica. Por tanto, resolver si P = NP conllevaría una auténtica revolución. Pero tranquilos que por el momento la cosa no parece siquiera mínimamente abordable. Es un buen argumento cinematográfico, pero nada más.
Aunque la película se estrenó en 2012, el borrador original del guion se escribió en 2009, años antes de que se revelara información filtrada de la NSA (Agencia Nacional de Seguridad norteamericana) que detallaba el ciberespionaje, un tema que se discute directamente en la película.
El rodaje con los planos esenciales se hizo en tan solo 10 días. No parece extraño, no sólo por el presupuesto sino también porque la mayor parte de la “acción” son debates y conversaciones entre los protagonistas, que tampoco son muchos.
La película ganó 3 premios en el Festival de Cine de Silicon Valley de 2012: Mejor Largometraje, Mejor Actor Principal y Mejor Montaje.
En los títulos de la película no aparece ningún consultor en ningún campo relacionado con lo que se trata en el argumento y bastantes afirmaciones matemáticas son incorrectas (o no verificadas, más bien). La película trata más sobre la moralidad de las acciones, por lo que no pretende ser una descripción real de las matemáticas o la informática.
El discurso grabado que se da durante la película termina exactamente a las 13:13:13:13, desde su inicio. Es difícil que haya sido casual, aunque no he encontrado ninguna referencia a que fuera algo premeditado.
Un par de diálogos comentados y algunas frases
Al inicio de la película, hablando de una adenda a un informe, uno de los protagonistas menciona a John Von Neumann:
- ¿Fue Von Neumann quien dijo que en matemáticas no entendemos las cosas, simplemente nos acostumbramos a ellas?
Tras opinar y discutir llegan a la conclusión de que en realidad lo que involucra la frase es “el conocimiento es poder”. Y sobre Neumann, declaran: “Su breve carrera, sin dudarlo, nos ha tocado, influido y motivado a todos nosotros”.
Cuando se hace la presentación de los protagonistas, desde luego son a cada cual más competente. Principalmente el protagonista, el doctor Timothy Horton, con una tesis sobre la hipótesis de Riemann, fellow invitado en el instituto para estudios avanzados y en el MIT, en donde su trabajo sobre la teoría de la complejidad le valió el premio Abel. Además miembro del Trinity College, fue propuesto a la medalla Fields por su demostración sobre la no existencia de las funciones unidireccionales (ya que tenemos que elegir a alguien relevante, que lo tenga todo, ¿verdad? Cuesta creer que alguien con essa trayectoria fuera tan joven como el actor que han elegido para interpretarlo).
Otra forma de transmitir relevancia e interés de cara al espectador que no conozca demasiado, es el hecho de citar a científicos, instituciones o sucesos importantes. Así, lo que setraen entre manos los reunidos allí dicen ser equiparable a “como Oppenheimer y Fermi posiblemente no pudieron predecir las consecuencias de la investigación de Los Alamos”. Esto los carga además de una atmósfera de cierta responsabilidad.
En la imagen, una pausa en el rodaje.
En uno de los muchos diálogos que se mantienen a lo largo de la película (en realidad toda la película es un diálogo, prácticamente una pieza teatral), se van citando algunas de las aplicaciones que las matemáticas han posibilitado (algunas cosas las explico entre paréntesis en color rojo; estos comentarios no aparecen en la película, obviamente): “La aplicación extraordinaria de las matemáticas nos ha permitido lujos y necesidades como los teléfonos móviles, la navegación GPS, el lavavajillas automático, los juegos de ordenador, los televisores portátiles, los reproductores de discos compactos. Nos ha permitido disfrutar de la alta definición, de la distribución de alimentos orgánicos, los aviones, los relojes de pulsera con calculadora. Nos ha permitido el radio control, la cirugía ocular LASIK (Laser assisted in Situ Keratomileusis, LASIK, es una cirugía refractiva para la corrección de la miopía, hipermetropía y astigmatismo. La realiza un oftalmólogo que utiliza un láser de baja potencia para cambiar de manera permanente la forma que tiene la córnea, con el fin de mejorar la visión y reducir la necesidad de la persona de usar gafas o lentes de contacto), la lectura del cerebro con láser, la artroscopia no invasiva. Nos ha permitido el 5G, los C-4 (un tipo de explosivo plástico), y las armas U-235 (el uranio 235 es el único isótopo natural fisible, es decir, el único isótopo presente en la naturaleza con capacidad para provocar una reacción en cadena de fisión nuclear). Nos han permitido los corazones artificiales, y la despiadada inteligencia artificial. Nos han proporcionado las blackberries, …., espero que estén todas en silencio ..., iPhones y todos los demás dispositivos portables que esclavizan al hombre, nos mantienen encadenados a la siempre creciente contingencia corporativa de este mundo. Nos ha permitido Facebook, MySpace, y todas las demás aplicaciones web que permiten una despiadada competencia y aceleran la infiltración codiciosa (se refiere al conocimiento de nuestros datos, gustos, a partir de los que nos muestran anuncios, nos proponen compras, etc.), y la perversión de nuestra juventud. En resumen, nos permite lo bueno, lo malo, y todo lo demás”.
Otra reflexión que se hace en la película:
- Una habitación con los cuatro hombres más inteligentes del planeta, y sin embargo ninguno de ustedes ha señalado nada con el entendimiento de la realidad del mundo. Los futuros conflictos no se librarán en una carrera hacia Júpiter o dividiendo átomos, o construyendo dispositivos nucleares más rápido que el otro. No. Esto es mucho más sutil. Es un centavo aquí, un centavo allí. Una red eléctrica que no responde, una bolsa de valores subvertida. El efecto acumulativo hace girar la economía mundial, y cuando el polvo se asiente, el mundo dividido será más pequeño. Como buitres a un cadáver gordo y carnoso. Quizás todavía somos una superpotencia. Quizás no lo somos. Pero no se equivoquen, caballeros. Los cartagineses llaman a la puerta, a las puertas de América.
- ¿Está insinuando que una red fantasma se está volviendo una amenaza más significativa?
- Mira, obviamente no tengo la libertad para discutir eso, pero basta con decir que los chinos son una constante fuente de escrutinio de nuestra comunidad de seguridad. Creo que eso responde la pregunta con bastante claridad.
- ¿De qué manera?
- Con la búsqueda y el descifrado acelerados de claves, el mundo entero está a tu alcance. Literalmente no hay nada que no se pueda ver, hasta que codifiquen las cosas de manera diferente, o desarrollen una arquitectura diferente antes de llegar a nosotros. Pero hasta ese momento tendríamos unos cuántos meses o años de acceso absoluto y sin vigilancia a lo que quisiéramos: información financiera, información técnica, datos militares, secretos nacionales codificados.
- Es el equivalente de ...
- Miles de millones. No, tendría que decir que billones de dólares en información.
- Caballeros ...
- No estoy seguro de que realmente se pueda poner un valor a ese nivel de información.
- Es cierto, pero podemos cuantificar aproximadamente las cosas aquí. ¿Correcto? Quiero decir, pensemos. El PIB chino ronda los 3,2 billones de dólares estadounidenses. A cualquier criptosistema que utilice algoritmos Pspace, que es esencialmente toda su infraestructura, se puede acceder fácilmente.
- Bueno, eso puede funcionar para un aspecto particular de una red, digamos, los registros de una institución financiera, pero otros sistemas utilizan un algoritmo criptográfico diferente.
- ¡Vamos!.
- No puedes crackearlo, porque es un problema diferente.
- Eso es absolutamente ridículo. Ni siquiera estamos hablando de teoría de vanguardia aquí. Gary Johnson, chicos, en los 70, demostró que, fundamentalmente, todos estos complejos problemas matemáticos ... Mochila, SAT (se refiere al problema de Satisfacibilidad Booleana, el primer problema identificado como NP-completo en 1971), lo que sea ..., Son todos el mismo problema.
- Resuelve uno, resuelve todos.
- Eso es lo que es esto. Eso es lo que significa NP- Completo.
- La Criptografía moderna se basa en, supongo, una realidad ahora obsoleta en la que algunos problemas son demasiado costosos computacionalmente para tratarse mediante fuerza bruta, ¿verdad? Utilizan demasiado tiempo para verificar todas las respuestas. Así se presenta el procesador no determinista. Y problemas que una vez emplearon millones de años en ser resueltos, resueltos en minutos.
- Agradezco la conferencia, y entiendo los fundamentos, pero mis chicos, y la investigación teórica apunta al hecho de que redes separadas requieren rejillas separadas con problemas computacionales diferentes.
- Oh, ¿tus chicos?
- Sí, Rand. Todo se reduce al oráculo no determinista. Con él, con el procesador, todos los problemas en el espacio P y NP se pueden calcular en un tiempo razonable. Búsquedas clave, factorización, registros discretos ... puedes romper cualquier criptosistema en el mundo si tienes la voluntad y, supongo, el programa de software para hacerlo. Ni siquiera un criptosistema híbrido chino podría prevenir o incluso reconocer un ataque.
- No.
- De todos modos, en mi opinión, esto funciona más como un arma, supongo, por resta o destrucción, de la misma manera que un arma convencional, a diferencia de, digamos, algún tipo de, no lo sé,…
- Hurto intergubernamental.
- ¿En qué sentido?
- En el sentido de que no es práctico malversar dinero chino para, digamos, financiar un proyecto de ley de educación, ¿de acuerdo? Si quieres mas dinero, simplemente imprime más. Y a este nivel, tendrá poco efecto en su economía. Y, si te descubren de alguna manera, básicamente, le has declarado la guerra a una superpotencia, y todo lo que tienes que demostrar para ello son algunas escuelas más limpias.
- Bueno, podría ser peor. Realmente, la única forma en que lo veo sería atacar sistemáticamente el activo. Básicamente, paralízalo, sácalo.
- Debo decir que es mucho más fácil discutir la aplicación cuando se contextualiza así.
- Supongamos que está a punto de lanzar un ciberataque contra China, ¿cuál sería lógicamente su primer objetivo?
- Las plantas de energía.
- ¿Por qué harías eso?
- Mata el poder, sofoca la cuadrícula defensiva. El país sería el más vulnerable.
- Sí, pero si cortas la energía, entonces no hay nada conectado ... ¿Cómo se puede piratear una red que no está en línea? No, creo que si quieres usar esto como arma, primero, aplasta todo su sistema de comunicaciones, actúa básicamente como el cerebro del país. Puedes recibir y transmitir lo que quieras. Histeria masiva, paranoia. Casi como una toxina a base de agua. Podrías destrozar el país.
Si algún lector lo desea, aquí pueden acceder al tráiler de la película.
Entre las “perlas” que se publicaron sobre la película, me llama la atención esta, de Plus Magazine: “"Travelling Salesman es una película inusual: a pesar de que casi todos los personajes son matemáticos, no hay ningún loco a la vista". ¡¡Menos mal que la publicación pretende acercar las matemáticas al personal de a pie!!
(Publicado en DivulgaMAT el 11 de febrero de 2021)
Comentarios
Publicar un comentario