LA CONJETURA DE HIRSCH

Como cualquier otro lenguaje, las matemáticas son fascinantes y adictivas...

Un matemático español cree que ha resuelto un problema de hace medio siglo

Francisco Santos, de la Universidad de Cantabria, anuncia que ha refutado la Conjetura de Hirsch

EL PAÍS - Madrid - 26/05/2010

La comunidad matemática internacional sigue con interés el trabajo de Francisco Santos, matemático de la Universidad de Cantabria, quien cree que ha resuelto un problema de más de 50 años de antigüedad, la llamada Conjetura de Hirsch. Aunque el resultado aún no ha sido publicado oficialmente algunos de los principales expertos del área ya lo han revisado, informa el servicio de información i-Math. Santos (Valladolid, 1968) es catedrático de Geometría y Topología y dice 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 supone, por tanto, 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 simplex y sirve desde para asignar horarios y turnos en grandes empresas hasta para planificar la producción o las 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 10 "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, un aspecto importante de cara a las aplicaciones. Lo que viene a decir la conjetura es que hay un límite determinado para la complejidad del algoritmo del simplex, 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 el matemático.

Santos empezó a pensar en el problema en 2002 a raíz de un encuentro en Seattle (EE UU) con Victor Klee, un matemático ya entonces retirado pero autor de los avances más importantes hasta entonces en la Conjetura de Hirsch. "Durante una agradable conversación en el departamento de matemáticas Klee me preguntó:¿Por qué no tratas de demostrar que la Conjetura de Hirsch es falsa?", explica Santos. "Más tarde descubrí que Klee formulaba la misma pregunta a mucha gente, incluyendo a todos sus alumnos, pero la pregunta y la forma en que la planteó me hicieron sentir especial en ese momento".

En 2007, durante un año sabático en la Universidad de California, Santos se metió de lleno en el reto de Klee. Y hace poco tuvo su momento Eureka: "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".

El plan original de Santos era presentar su contraejemplo a la comunidad matemática el próximo julio en Seattle, en un congreso homenaje a Klee; así lo había adelantado en el resumen -ya público- de su intervención. Pero dado el interés suscitado lo presentará antes, en pequeñas reuniones en Francia, Suiza y Portugal las próximas semanas.

Si se dejan de lado las aplicaciones, la Conjetura de Hirsch dice cómo 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 Taiwan. Esto es lo que hace el algoritmo del simplex". 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?

¿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 simplex 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.