Un matemático español refuta la conjetura de Hirsch

El mes pasado, este profesor universitario, que dirige el Centro Internacional de Encuentros Matemáticos de Cantabria, anunció que había refutado la conjetura de Hirsch desarrollando el denominado "Teorema generalizado de los 'd' pasos". La importancia del descubrimiento, recuerda ahora la UC en un comunicado, radica en que abre una nueva línea de investigación sobre la complejidad de la programación lineal, un método de trabajo que se emplea para resolver cuestiones cotidianas como los cálculos de horarios o la organización de las redes de transporte. El artículo en el que Santos explica en 27 páginas su propuesta de refutación de la conjetura está disponible en esta página web de la Universidad de Cornell.

La hipótesis formulada por Warren M. Hirsch -que recibe el nombre de conjetura porque hasta la fecha no se ha podido demostrar ni refutar- se utiliza para predecir el nivel de complejidad que puede alcanzar el algoritmo del símplex. El símplex es un método empleado en geometría que también se utiliza en la vida diaria para resolver problemas de logística, de organización del trabajo, de estrategia de mercado, de inversión o incluso de diseño de redes. Un ejemplo de ello puede ser 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.

La conjetura establecía que hay un límite en la complejidad que puede alcanzarse al aplicar ese método, una suposición que hasta ahora había funcionado y que había resistido numerosos intentos de rebatirla. Francisco Santos asegura que ha hallado un ejemplo en el que la complejidad predicha por la conjetura se queda un 3 por ciento por debajo de la solución real, una diferencia que reconoce que es ligera, pero que supone "la ruptura de una barrera psicológica".

"Al tratarse de una conjetura que llevaba 50 años abierta, sin que nadie fuera capaz de demostrarla o rebatirla, cuando se encuentra una refutación, pues parece que se rompe una barrera psicológica. Se abre la veda y no se sabe muy bien dónde puede estar el límite", comentó al anunciar su descubrimiento este profesor de la UC, que hace diez años ya rompió otra conjetura sobre triangulación.