null

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

El hallazgo abre una nueva línea de investigación para resolver cuestiones cotidianas como los cálculos de horarios o la organización de las redes de transporte

Día 17/06/2010 - 22.56h
La Biblioteca de Cornell (EEUU) ha publicado en su espacio abierto de internet el artículo del profesor de Matemáticas de la Universidad de Cantabria (UC) Francisco Santos en el que se explica el contraejemplo que refuta la conjetura de Hirsch, un problema matemático pendiente de resolución desde 1957.
Un matemático español refuta la conjetura de Hirsch
abc 
La hipótesis de Hirsch se utiliza para predecir el nivel de complejidad de un algoritmo símplex

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.

  • Compartir
  • mas
  • Imprimir
publicidad
Consulta toda la programación de TV programacion de TV La Guía TV

Comentarios:

Sigue ABC.es en...

Investigadores insisten en la existencia de la primera supertierra descubierta en zona habitable, rechazada por otros estudios
José Manuel Nieves Encuentra aquí todos los vídeos del blog que te explica las noticias científicas
    Retos que ponen a prueba nuestra capacidad para el pensamiento lateral
    Lo último...

    Prueba los nuevos juegos web

    Copyright © ABC Periódico Electrónico S.L.U.