Ads-728

Ads-728

Psicología

Astrofísica

Genética

Neurociencia

» » » Un nuevo algoritmo que rompe 30 años de estancamiento

Referencia: Quanta Magazine.org .
"Landmark Algorithm Breaks 30-Year Impasse"
por Erica Klarreich, 14 de diciembre 2015
*******************************************
Los científicos informáticos son un hervidero tras el anuncio de un nuevo y rápido algoritmo capaz de resolver uno de los problemas centrales en el campo de la computación.
László Babai anunció su algoritmo de isomorfismo de grafos en la Universidad de Chicago el 10 de noviembre. crédito: Jeremy Kun
Un científico teórico de la computación ha presentado un algoritmo que está siendo aclamado como un gran avance en la cartografía del oscuro terreno de la teoría de la complejidad, que explora cómo resolver los difíciles problemas computacionales. El mes pasado, László Babai, de la Universidad de Chicago, anunció que había llegado a un nuevo algoritmo para el problema del "isomorfismo gráfico", uno de los misterios más tentadores de la informática. Este nuevo algoritmo, dice Babai, es mucho más eficiente que el mejor anterior, que había mantenido su récord durante más de 30 años. Su estudio está disponible en arxiv.org, y también lo ha presentado al 48º Simposio sobre Teoría de la Computación de la Asociación para Maquinaria de Computación .

Durante décadas, el problema del isomorfismo de grafos ha mantenido un estatus especial dentro de la teoría de la complejidad. Mientras miles de otros problemas computacionales han sucumbido mansamente a la categorización de fácil o difícil, el isomorfismo gráfico ha desafiado la clasificación. Parece más fácil que los problemas difíciles, pero es más difícil que los fáciles, ocupando una especie de tierra de nadie entre estos dos dominios. Es uno de los dos problemas más famosos de esta extraña zona gris, señaló Scott Aaronson, un teórico de la complejidad del Instituto de Tecnología de Massachusetts. Ahora, dijo, "parece que uno de los dos ha caído."


El anuncio de Babai ha electrificado a la comunidad científica de teoría computacional. Si su trabajo resulta correcto, será "uno de los grandes resultados de la década, si no de las últimas décadas", ha subrayado Joshua Grochow, científico computacional en el Instituto de Santa Fe.

Los informáticos usan la palabra "grafo" para referirse a una red de nodos con bordes conectados a algunos de los nodos. La cuestión del isomorfismo de grafos se pregunta simplemente cuándo dos grafos son realmente el misma grafo disfrazado, ya que hay una correspondencia de uno-a-uno (un "isomorfismo") entre sus nodos que conserva las formas en que los nodos están conectados. El problema es fácil de enunciar, pero difícil de resolver, ya que incluso los grafos pequeños se pueden parecer muy diferentes con tan sólo mover sus nodos alrededor.

Ahora, Babai ha tomado lo que parece ser un gran paso adelante en la fijación del nivel de dificultad del problema, al establecer lo que él afirma es un algoritmo "cuasi-polinómico de tiempo" a resolver. Como Aaronson describe, el algoritmo coloca el problema dentro de "una gran área metropolitana" de P, la clase de problemas que pueden ser resueltos de manera eficiente. Si bien este nuevo trabajo no es la última palabra sobre la dificultad del problema del isomorfismo de grafos, los investigadores lo ven como un cambio de juego. "Antes de anunciarlo, no creo que nadie, excepto tal vez, él, pensara que se conseguiría un resultado en los próximos 10 años, o incluso nunca", añadió Grochow.

En las últimas semanas, Babai dio cuatro charlas que describen su algoritmo. Tomará tiempo para que pueda ser revisado a fondo por otros expertos. Babai se ha negado a hablar con la prensa, que escribió en un correo electrónico: "La integridad de la ciencia requiere que, los nuevos resultados deban ser sometidos a una revisión exhaustiva por colegas expertos, antes de que los resultados se publiquen en los medios de comunicación."

Otros investigadores están cautelosamente esperanzados de que su prueba dé resultados. "Babai tiene un historial admirable", comentó Aaronson.

"Creo que la gente es muy optimista en ello", apuntó Luca Trevisan, científico de computación en la Universidad de California, Berkeley, tras la segunda charla de Babai. Si la prueba resulta correcta, dijo, "se trata de un resultado histórico."

**********************
Más información: Quanta Magazine.org .

,

«
Next
Entrada más reciente
»
Previous
Entrada antigua
Editor del blog Pedro Donaire

Filosofía

Educación

Deporte

Tecnología

Materiales