Un matemático español resuelve un problema de hace medio siglo
Escrito por Redacción Matematicalia   
miércoles, 26 de mayo de 2010
Image LA CONJETURA DE HIRSCH FUE ENUNCIADA EN 1957 Y HASTA AHORA HABÍA RESISTIDO TODOS LOS INTENTOS PARA DEMOSTRARLA O REBATIRLA. El problema tiene que ver con un algoritmo muy usado para optimizar recursos en la empresa. La solución de Santos ha resultado más sencilla de lo esperado, y abre nuevas vías de investigación.

Madrid, 26 de mayo.- La comunidad matemática internacional, o al menos una parte relativamente importante de ella, lleva varios días de revuelo. Ha 'caído' un problema de más de cincuenta años de antiguedad, la llamada 'Conjetura de Hirsch', gracias al trabajo del matemático de la Universidad de Cantabria Francisco Santos. Aunque el resultado aún no ha sido publicado oficialmente algunos de los principales expertos del área ya lo han revisado, y los blogs matemáticos bullen de actividad. Santos 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 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' 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. Este aspecto, cómo de complejo sea un algoritmo, es importante de cara a las aplicaciones, dado que más 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 Santos. "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-.

UNA AGRADABLE CONVERSACIÓN

Image

Santos empezó 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. "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 hizo 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.

EN EL METRO: ¿POR QUÉ RUTA HAY QUE HACER MENOS TRANSBORDOS?

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.

SOBRE FRANCISCO SANTOS

Francisco Santos Leal (Valladolid, 1968) es catedrático de Geometría y Topología en la Universidad de Cantabria. Es un experto internacionalmente reconocido en “Triangulaciones de politopos -un politopo es una forma geométrica equivalente al polígono en el plano (2-D) y al poliedro en el espacio (3-D), pero en cualquier número de dimensiones-. Es un investigador básico y su principal motivación “es puramente estética” –afirma-, pero la triangulación de politopos tiene aplicaciones en topografía, resolución numérica de ecuaciones de varias variables, en diseño geométrico...

La Conjetura de Hirsch no es la primera conjetura que refuta Santos. En el año 2000 descubrió una determinada triangulación de un politopo con propiedades sorprendentes, que alguien había conjeturado que ninguna triangulación podría tener. Santos fue uno de los conferenciantes invitados en el Congreso Internacional de Matemáticos ICM 2006, celebrado en Madrid.

Más información: Francisco Santos, Universidad de Cantabria
Tel: 618302879
Esta dirección de correo electrónico está protegida contra los robots de spam, necesita tener Javascript activado para poder verla
http://personales.unican.es/santosf/

BLOG MATEMÁTICAS Y SUS FRONTERAS
http://www.madrimasd.org/blogs/matematicas/2010/05/23/131798

i-MATH:
Ingenio MATHEMATICA (i-MATH) es un proyecto CONSOLIDER de investigación con el objetivo básico de promover y ejecutar actuaciones que incrementen cualitativa y cuantitativamente el peso de las matemáticas en el panorama internacional y en el sistema español de ciencia, tecnología, empresa y sociedad. http://www.i-math.org
Gabinete de Comunicación i-MATH
Mónica Salomone: 649 934 887/Jesús Hidalgo 667819726
Telf: 917424218
Esta dirección de correo electrónico está protegida contra los robots de spam, necesita tener Javascript activado para poder verla

BLOG DIVULGATIVO DE MATEMÁTICAS
Blog para antimatemáticos. Crónicas de una periodista entre números: http://blog.i-math.org/
Twitter :https://twitter.com/_imath