miércoles, 26 de mayo de 2010

Un español resuelve un problema matemático de hace medio siglo, la Conjetura de Hirsch


La comunidad matemática lleva varios días de revuelo. La llamada 'Conjetura de Hirsch' ha sido resuelta gracias al trabajo del matemático de la Universidad de Cantabria Francisco Santos, según ha informado 'i-Math'.
Aunque el resultado aún no ha sido publicado oficialmente algunos expertos del área ya lo han revisado, y los blogs matemáticos bullen de actividad. Santos afirma que ha dado con una solución más sencilla de lo que él mismo esperaba.
En matemáticas, una conjetura es una afirmación hecha sin pruebas y por tanto supone un reto para los investigadores, que deben demostrar que es cierta o falsa. La Conjetura de Warren M. Hirsch (1918-2007) fue enunciada en 1957 y desde entonces ha sido objeto de numerosos 'ataques', que no han tenido éxito: "Ha resistido bastante bien el paso del tiempo", afirma Santos.
Esta Conjetura tiene que ver con un algoritmo útil, en última instancia, para optimizar recursos en numerosas aplicaciones. Se trata del 'algoritmo del símplex' (usado en una parte de las Matemáticas, denominada Programación Lineal) y sirve desde para asignar horarios y turnos en grandes empresas hasta para planificar producción o carteras de inversión; formular estrategias de mercado; o diseñar redes ferroviarias, aéreas o de carreteras. Es por tanto un algoritmo con gran impacto en el ámbito industrial - de hecho es uno de los diez "más influyentes en el desarrollo de la ciencia y la ingeniería del siglo pasado", según una selección elaborada por expertos para la revista Computing in Science and Engineering -.
La Conjetura de Hirsch está relacionada con la complejidad de este algoritmo. La complejidad implica, por ejemplo, más tiempo de cálculo -caro y escaso- en ordenadores. Lo que viene a decir la Conjetura es que hay un límite determinado para la complejidad del algoritmo del símplex.
Pero Santos demuestra que esto es falso: él ha encontrado un contraejemplo en el que el algoritmo es más complejo que el tope establecido por la conjetura. "Aunque mi contraejemplo supera este límite en relativamente poco, tiene el efecto de romper una barrera psicológica", explica. "Una vez que esa conjetura que parecía natural y que ha resistido tanto tiempo ha sido rota, ¿adónde podremos llegar? [en cuanto a complejidad]". Tal como quedan las cosas, ahora no se conoce límite alguno para lo difícil que puede volverse el algoritmo del símplex - y por extensión los problemas a los que se aplica -.
El matemático comenzó a pensar en el problema en 2002 a raíz de un encuentro en Seattle (EEUU) con Victor Klee, un matemático ya entonces retirado pero autor de los avances más importantes hasta entonces en la Conjetura de Hirsch.
En 2007, durante un año sabático en la Universidad de California, Santos se metió de lleno en el reto de Klee. "Pasas mucho tiempo dándole vueltas a las cosas y de repente un buen día te das cuenta de algo que puede ser una tontería, pero en la que no habías caído antes".
Santos iba a presentar su contraejemplo a la comunidad matemática el próximo julio en Seattle. Sin embargo, dado el interés suscitado lo presentará antes, en pequeñas reuniones en Francia, Suiza y Portugal durante las próximas semanas.

Si se dejan de lado las aplicaciones, la Conjetura de Hirsch dice cuánto de grande puede llegar a ser un poliedro (un cubo, una pirámide...) de cualquier dimensión. O, en otras palabras, cuántas aristas del poliedro hay que recorrer para conectar los dos puntos del poliedro más alejados entre sí.
Para eso se puede pensar en el poliedro como una red, en la que los nodos son los vértices. Santos pone un ejemplo: "La red puede estar formada por los vuelos de todas las compañías aéreas; los nodos son los aeropuertos, y lo que queremos saber es cuántos vuelos hay que coger para ir de Madrid a Taiwán. Esto es lo que hace el algoritmo del símplex". Otro ejemplo sencillo es el problema al que se enfrentan millones de personas cada mañana cuando deciden su ruta al trabajo: ¿Qué recorrido les supone un menor número de transbordos de metro?
Siguiendo los ejemplos, la Conjetura de Hirsch venía a decir que no es necesario superar un determinado número de vuelos, o transbordos.
Ahora bien, el cálculo se complica un poco en los casos en que se aplica habitualmente el algoritmo del símplex. En los problemas reales de hoy se trabaja con poliedros no de tres dimensiones, sino de miles y miles de dimensiones. De hecho, una de las características del ejemplo de Santos es que vive en sólo 43 dimensiones.
¿Qué implicaciones tiene este resultado? "Hubiera tenido más si hubiera demostrado que la conjetura es correcta. Lo que sí puede abrir vías interesantes para entender mejor el algoritmo del símplex es el método que he desarrollado para encontrar este contraejemplo", afirma el investigador de la Universidad de Cantabria. La Conjetura de Hirsch es falsa, pero el trabajo no ha terminado.

2 comentarios:

Anónimo dijo...

Francisco Santos encontró en un avión la solución a un problema matemático de hace medio siglo. Fue durante un viaje entre París y Bilbao cuando este profesor de la Universidad de Cantabria (UC) halló la inspiración para refutar la 'Conjetura de Hirsch', un enigma que la comunidad científica no ha podido desentrañar desde hace 53 años. «En lugar de hacer un sudoku, saqué papel y boli y, de pronto, me vino la idea», explicó a este periódico.
Warren M. Hirsch hizo una en 1957: «Un poliedro que tenga 'N' caras y dimensión 'D', su grafo no puede tener diámetro más grande que 'N-D'». Un trabalenguas para cualquiera que no tenga un diploma en ciencias, pero que Santos llevaba rumiando tres años. Incluso, escribió una recopilación sobre los estudios realizados y hablo sobre ella en la Real Sociedad Matemática Española el año pasado.
Pero, ¿para que sirve la 'Conjetura de Hirsch'? «Forma parte del Método Simplex, un algoritmo que todas las empresas del mundo utilizan en la actualidad para diseñar carreteras, planificar producciones, carteras de inversión o turnos de trabajo», señaló Santos.
Y puso varios ejemplos. Una compañía aérea con 2.000 azafatas necesita un programa que utilice el algoritmo para distribuir sus vuelos, y que una azafata que esté en Roma no tenga que coger un avión en Moscú ese mismo día. También puede determinar en una red urbana de metro cuál es la ruta para ir de un punto a otro haciendo el menor número de transbordos. «Es una ecuación que permite ordenar muchas variables», resumió este profesor.
«Este algoritmo funciona muy bien, pero lo que no sabemos es porqué», indicó Santos. Y eso es lo que Hirsch quiso explicar con su conjetura. Es decir, su teorema ponía límites a la complejidad del Simplex, y lo que ahora hace Santos es romper las fronteras puestas por Hirsch. O más bien, demostrar que esas barreras no existen. Santos lo ha conseguido con un poliedro que tiene 86 caras y 43 dimensiones. «He desmontado la teoría por muy poco, sólo por un 3%», confesó Santos, de 42 años y director del Centro Internacional de Encuentros Matemáticos (CIEM) de Castro Urdiales.
Este profesor admite que una desviación del 3% «no tiene la menor importancia» desde el punto de vista de «una persona que está utilizando un algoritmo para resolver sus problemas de optimización». «Pero al tratarse de una conjetura que llevaba 50 años abierta, sin que nadie fuera capaz de demostrarla o rebatirla, en el momento que se encuentra una refutación, se rompe una barrera psicológica. Se abre la veda y no se sabe muy bien dónde puede estar el límite», argumentó Santos, que en el año 2000 ya rompió otra conjetura sobre triangulación.
La importancia del logro de Santos no se limita sólo a la comunidad científica. El Método Simplex es uno de los algoritmos incluidos en el 'Top Ten' de los más influyentes del siglo pasado, según la revista Computing in Science and Engineering.
Santos está centrado ahora en terminar de escribir el artículo con todos los detalles técnicos de la refutación.
Ahora, con el revuelo mediático que se ha creado, Santos lo enviará inmediatamente a las revistas más prestigiosas de ciencia y lo 'colgará' en Internet.
Ayer por la tarde su teléfono «no dejó de sonar». Medios de comunicación, amigos, compañeros de profesión... sin embargo, Santos comprobó la trascendencia de su descubrimiento el pasado 10 de mayo. «Hice un resumen para lo del Congreso de EE UU y ese mismo día, en la página de Wikipedia dedicada a la conjetura ya incluían mi trabajo», explicó. Poco después, uno de los blogs más prestigiosos sobre matemáticas también publicó la noticia y muchos científicos empezaron a llamar al teléfono de Santos.
Este profesor cántabro también quiso guardarse las espaldas, y antes de hacerlo público envió un borrador a quince colegas suyos. «Lo leyeron y lo aceptaron», confirmó.
Santos se dedicará ahora a refutar con mayor margen la teoría de Hirsch. Para conocer el porqué del éxito de Simplex habrá que esperar todavía.

Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.