|
Travelling Salesman
Ficha técnica.- 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. 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",
Los problemas de complejidad
llamada "P" son aquellos para los
que existe un algoritmo
que encuentra su solución en tiempo polinómico.
“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
|