Matemáticas

en tu mundo

Matemáticas y Cine

 

 

TRAVELLING SALESMAN

 

Travelling Salesman (Timothy Lanzone. 2012) es una película todavía no estrenada en España, donde probablemente se titulará El problema del viajante (nunca se sabe…). Viene avalada por 3 premios en el Festival de Cine de Silicon Valley y por unas excelentes críticas. La propia web oficial del film lo califica como “thriller intelectual”, género que comenzó de forma hasta ahora solitaria con Primer (Shane Carruth. 2004). Dado que  las matemáticas están en el núcleo de su argumento presentamos una recopilación de información sobre esta prometedora película, a la espera de poder verla y analizar sus escenas matemáticas.

Argumento (de la web oficial, http://www.travellingsalesmanmovie.com).- 

Cuatro matemáticos han resuelto el problema más difícil en la historia de la informática: P = NP. Los cuatro han creado conjuntamente un "sistema" que podría ser el próximo gran avance para nuestra civilización pero también podría destruir la humanidad.
La solución del problema podría aplicarse inmediatamente en la informática, pero su aplicación no tardaría en extenderse a un sinnúmero de otras disciplinas. Por ejemplo, utilizando la solución de P = NP, un hacker podría romper los códigos de cifrado más avanzados en cuestión de segundos, una tarea que ahora lleva semanas, meses o incluso años. Podría entrar en el control del tráfico aéreo o en la red china de comunicaciones. Sin embargo, el algoritmo matemático también serviría como la base para la investigación biológica acelerada, para la curación de enfermedades tales como el SIDA y el cáncer.

Comienza la película con la cita en un lugar secreto de los cuatro matemáticos con un alto funcionario del Departamento de Defensa estadounidense. El grupo discute las implicaciones globales de la solución del problema y están de acuerdo en que deben ser extremadamente responsables sobre quiénes podrán tener acceso a su descubrimiento.

Se les ofrecen 10 millones de dólares a cada uno a cambio de su parte del algoritmo de la solución. Se abordan con destreza sus preocupaciones y dudas. Al final, sólo un matemático se opondrá a  la venta de la solución. A medida que los matemáticos están a punto de firmar los documentos que darán al gobierno de los EE.UU. la propiedad exclusiva y privada de su solución, luchan con el dilema moral de cómo será utilizado un descubrimiento tan sensible. La matemática es real. Sus consecuencias son reales.

 

 

Comentario (varias fuentes, corregido con la valiosa aportación de Alberto Márquez).- 

El “problema del viajante” se puede enunciar así: Si un viajante debe recorrer varias ciudades partiendo de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitarlas todas minimizando la distancia total recorrida y terminando en A?

Este es el problema de optimización más famoso de combinatoria computacional. Su algoritmo de solución teórica es conocido, pero llevarlo a la práctica puede requerir demasiado tiempo. Es un ejemplo de ciertos problemas matemáticos que a priori parecen tener una solución relativamente fácil y en la práctica son muy complejos.

La solución más directa consiste en analizar todos los posibles recorridos, valorando la suma de las distancias en cada caso. Pero el número de recorridos posibles es el factorial del número de ciudades (n!) y la complejidad se dispara. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.147 años en resolver el problema para sólo 20 ciudades. Las rutas posibles entre 12 ciudades son 479.001.600. Se puede demostrar que la condición de volver a la ciudad de partida no cambia la complejidad del problema. En el año 2001 se utilizó una red de 110 ordenadores para resolver el problema con las 15.112 poblaciones de Alemania, utilizando el equivalente computacional a 22,5 años de un PC (Wikipedia).

Una formulación equivalente en términos de teoría de grafos es la de encontrar en un grafo completamente conexo y con arcos ponderados el ciclo hamiltoniano de menor coste. En esta formulación cada vértice del grafo representa una ciudad, cada arco representa una carretera y el peso asociado a cada arco representa la longitud de la carretera. Este es uno de los problemas de complejidad llamada "NP", para los que se puede comprobar si una solución es válida en tiempo polinómico en función del tamaño de la entrada (en este caso del número n de ciudades que el viajante debe recorrer). Algunos casos concretos del problema han sido resueltos hasta su optimización, lo que lo convierte en un excelente banco de pruebas para algoritmos de optimización en situaciones isomorfas.

Los problemas de complejidad llamada "P" son aquellos para los que existe un algoritmo que encuentra su solución en tiempo polinómico. Por lo tanto es evidente que P es un subconjunto de NP y el gran problema es determinar si P = NP. Para resolver este problema, bastaría con encontrar un algoritmo polinómico para cualquiera (basta uno) de los problemas de otra subclase de NP (los llamados problemas NP-completos). El Travelling Sales Problem no es NP-completo (pertenece a otra clase llamada NP-duro), pero si se puede resolver en tiempo polinomial, entonces existe una versión equivalente entre los problemas NP-completos que se puede resolver en tiempo polinomial y por tanto P=NP

“P = NP” es uno de los problemas sin resolver más famosos. Fue presentado por primera vez en 1971 y se pregunta si es posible resolver todos los problemas NP tan rápidamente como los problemas P. De momento, nadie lo sabe a ciencia cierta. La supuesta inclusión estricta entre las clases de complejidad P y NP es una de las cuestiones abiertas más importantes de las matemáticas. El Instituto Clay de Matemáticas (Cambridge, Massachusetts) premia con un millón de dólares a quién sea capaz de lograr su resolución.

Algunos problemas NP a día de hoy requieren mucho tiempo, como la programación logística y de predicción de estructura de proteínas. Del mismo modo, muchos sistemas de encriptación de datos basan su seguridad en la suposición de que no pueden ser resueltos en un tiempo polinómico. Si alguien llegase a demostrar que los problemas P y NP son de dificultad equivalente estableciendo el método de resolución, el descubrimiento tendría importantes consecuencias prácticas. Por ejemplo, gran parte de la criptografía moderna quedaría al descubierto y los sistemas financieros serían vulnerables.

Travelling Salesman acerca al gran público la relevancia social y el calado ético que pueden llegar a tener esas ignoradas matemáticas. Las críticas norteamericanas hablan de seriedad y rigor en el intento. Ojalá pronto podamos dar nuestro veredicto.

  

 

  

  

 

 

       

 

 

 

 

 

 

 

 

 

 

(C) José María Sorando Muzás

jmsorando@ono.com