Un catedrático dice haber refutado la “conjetura de Hirsch”

Un catedrático cántabro dice haber refutado la “conjetura de Hirsch” MAdridmasdWikipedia:

CIEM (International Center for Mathematical meetings) is a join initiative of the University of Cantabria and the City Council of Castro Urdiales   -  http://www.ciem.unican.es/

Conjetura de Hirsch resuelto

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

Lo que viene a decir la Conjetura es que hay un límite determinado para la complejidad del algoritmo del símplex.

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”.

La Vanguardia – Santander, 26 may (EFE).- El catedrático de Geometría de la Universidad de Cantabria (UC) Francisco Santos ha anunciado hoy que ha refutado la “conjetura de Hirsch”, una teoría que predice hasta qué punto puede resultar complejo un algoritmo empleado en varios ámbitos de la vida y que se resistía desde su enunciación, en 1957.

La conjetura formulada por Warren M. Hirsch -que recibe esa denominación, conjetura, porque hasta la fecha no se ha podido demostrar ni refutar- se utilizaba 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, según ha explicado a Efe Francisco Santos.

Este catedrático de la UC prepara un artículo en el que explica 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”.

Santos admite que una desviación del 3 por ciento “no tiene la menor importancia” desde el punto de vista de “una persona que está corriendo 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, 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”, argumenta este profesor de la UC, que en el año 2000 ya rompió otra conjetura sobre triangulación.

Francisco Santos asegura que llevaba “dándole vueltas” a la conjetura de Hirsch desde hace más de dos años y que la clave que le condujo a la solución se le ocurrió durante un vuelo de París a Bilbao, desarrollando una idea que ya había apuntado en los años sesenta el matemático Víctor Klee, al que conoció en 2002.

“Klee ya había hecho una especie de reducción de la conjetura. Había demostrado que esa conjetura tan general era equivalente a un cierto caso particular y que, por lo tanto, en lugar de pensar en el caso general, bastaba con centrarse en el particular. A mí se me ocurrió que se podía ir un poco más allá en ese teorema de Hirsch, para reducir la teoría un poco más”, relata.

En el mundo científico, las demostraciones o refutaciones de teorías son admitidas cuando se publican en revistas de prestigio, que a su vez suelen someter los artículos que reciben al filtro de la opinión de expertos en esa disciplina.

Santos asegura que todavía esta puliendo los detalles del artículo en el que explica su solución, pero también alega que “los tiempos han cambiado” y que el campo de juego hoy es internet.

Y como ejemplo cita el caso del matemático ruso Grigori Perelman, que en 2002 colgó en la red su demostración de otra conjetura famosa, la de Poincaré, considerada uno de los siete problemas del milenio. Aunque Perelman no llegó a publicar su explicación en ninguna revista, su tesis hoy está generalmente aceptada. EFE

This entry was posted in .. Bookmark the permalink.

Comments are closed.