- Noticias
16/01/2017
TEORÍA DE LA COMPUTACIÓN
El autor del ambicioso resultado repara el error hallado en su demostración cinco días después de haberla retirado.
Quanta Magazine
El problema del isomorfismo de grafos consiste en encontrar un algoritmo computacional capaz de determinar con rapidez si dos grafos con el mismo número de vértices pero distinta apariencia comparten o no la misma estructura básica. [aleksandarvelasevic/iStock]
Han sido dos semanas convulsas para los teóricos de la computación. El pasado 4 de enero, László Babai, catedrático de la Universidad de Chicago, impactaba a la comunidad tras retractarse de un resultado que, en noviembre de 2015, los expertos de la disciplina habían aclamado como el logro de la década. Poco después, el 9 de enero, Babai anunciaba que había corregido el error presente en su demostración. Y cinco días más tarde, el 14 de enero, el matemático que había identificado el problema en el trabajo de Babai —el peruano Harald Helfgott, de la Universidad de Gotinga y el CNRS francés— confirmaba públicamente que la nueva demostración de Babai era correcta en una charla impartida en el seminario Bourbaki de París, uno de los ciclos de conferencias más reputados en matemáticas.
El tira y afloja se refiere al problema del isomorfismo de grafos. Este plantea si dos grafos (redes formadas por nodos y enlaces) de apariencia distinta comparten o no la misma conectividad subyacente. A pesar de lo simple que resulta de enunciar, los teóricos de la computación llevan más de 30 años intentando averiguar si existe un algoritmo capaz de resolverlo de manera eficiente.
El resultado de Babai presenta un algoritmo para solucionar el problema en tiempo «cuasipolinómico». En términos muy simplificados, ello hace que el problema del isomorfismo de grafos cruce prácticamente todo el océano que separa los problemas que no pueden resolverse de manera eficiente de los que sí. Ahora, chapotea en las someras aguas situadas frente a la costa de aquellos problemas que sí pueden solucionarse de forma eficiente; es decir, en una cantidad de tiempo de cómputo que los expertos denominan «polinómica».
Helfgott había pasado meses estudiando el algoritmo que Babai publicó en 2015 para preparar su charla en el seminario Bourbaki. Al analizarlo en detalle, se percató de la existencia de un sutil error en un paso conocido como «dividir o Johnson» (split-or-Johnson). Este implica simplificar el problema del isomorfismo de grafos, bien mediante la identificación de «grafos de Johnson» entre los dos grafos que se están comparando, o bien encontrando una manera de colorear los grafos que respete sus simetrías, lo que facilita comparar su estructura.
El procedimiento en cuestión incluía un paso recursivo en el que cierta subrutina dividía el problema en dos piezas menores y después se llamaba a sí misma para ejecutarse de nuevo en ellas. Sin embargo, cada vez que la subrutina se ejecutaba, introducía cierto factor de corrección para dar cuenta de la exactitud con que las coloraciones reflejaban la simetría de los grafos, y esos errores se acumulaban de manera incontrolada. En un procedimiento con ese tipo particular de crecimiento de errores, «semejante bifurcación en la recursión es completamente desastrosa», señala Helfgott en un correo electrónico. Ahora Babai ha averiguado cómo hacer que la subrutina se llame a sí misma sin bifurcarse en cada paso. «Confío en que la demostración es correcta», escribe Helfgott.
Babai está trabajando en una versión revisada de su artículo, la cual incluirá el nuevo ajuste así como otros cambios en respuesta a los comentarios recibidos durante el último año. El investigador explica por correo electrónico que espera publicar un nuevo borrador en línea aproximadamente dentro de un mes.
Más información en Quanta Magazine (14 de diciembre de 2015, 5 de enero de 2017), el blog de Helfgott y la página web de Babai. Una versión de la demostración original de Babai puede encontrarse en el repositorio arXiv.
—Erica Klarreich/Quanta Magazine
Este artículo fue publicado originalmente en QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión pública de la ciencia.
