La afirmación de un profesor de haber creado un algoritmo que simplifica drásticamente uno de los problemas más famosos de la informática teórica ha hecho que los expertos se preparen para reconsiderar una verdad consolidada de su campo. También ha servido como recordatorio de que es posible realizar avances algorítmicos similares que podrían debilitar los problemas difíciles de resolver que se encuentran en el corazón de la criptografía que protege los secretos digitales de todo el mundo.
En un salón de actos abarrotado, el profesor László Babai de la Universidad de Chicago (EEUU) dio el martes y jueves de la semana pasada las primeras dos ponencias de una serie de tres que describen su nueva solución para un problema llamado el isomorfismo de grafos. El problema pide a un ordenador que determine si dos grafos distintos – en el sentido de un conjunto de "nodos" conectados a una red, como un grafo social – realmente son representaciones distintas de lo mismo.
Las ponencias de Babai han suscitado un gran entusiasmo porque el isomorfismo de grafos es conocido como un problema extremadamente difícil que durante más de 30 años se ha creído que no dista mucho de la clase de problemas más difíciles para los ordenadores. Si Babai tiene razón, realmente se acerca mucho más a la clase de problemas que pueden resolver los ordenadores de forma eficiente, una categoría conocida como P (ver ¿Qué significa 'P vs NP' para el resto de nosotros?).
"Esto ha captado la imaginación de todos porque la mejora es muy grande", dice Richard Lipton, un profesor que trabaja en la ciencia informática teórica en el Instituto de Tecnología de Georgia (EEUU). "Lo ha bajado a una clase de una dificultad mucho más baja". Después de escuchar el reclamo de Babai, el profesor adjunto del Instituto Tecnológico de Massachusetts (MIT, EEUU) Scott Aaronson escribió en su blog que podría ser "el resultado de la década en la informática teóricas".
Los informáticos miden la dificultad de un problema al analizar cuánto crecen los recursos computacionales que necesita un algoritmo para resolverlo mientras aumente el tamaño del problema original. El isomorfismo de grafos es considerado extremadamente difícil porque la necesidad de recursos del mejor algoritmo conocido aumenta exponencialmente según crece el tamaño de los grafos sobre los que trabaja.
Ese algoritmo fue publicado en 1983 por Babei junto a Eugene Luks de la Universidad de Oregon (EEUU). Babai afirma que su nuevo algoritmo experimenta un aumento mucho menos pronunciado de los recursos requeridos mientras se agranden los grafos sobre los que trabaja, bajando así de forma significativa la dificultad del isomorfismo de grafos.
Babai rehusó realizar una entrevista, diciendo que no sería apropiado darles publicidad antes de terminar de describir sus resultados detalladamente en un trabajo y antes de que este fuera examinado por sus iguales. Le contó a un asistente entusiasmado de su primera ponencia que una prepublicación se emitirá "muy, muy pronto".
Lipton recomienda precaución siempre que se afirme haber logrado un avance sin la publicación de un trabajo detallado, pero que la reputación de Babai hace que muchas personas de este campo de investigación crean que sus resultados son reales. "Hablamos de un investigador estelar", dice Lipton.
Si se confirma el resultado de Babai, el efecto no se percibirá demasiado fuera del mundo enrarecido de los expertos en la complejidad computacional. El isomorfismo de grafos puede aplicarse a algunas situaciones prácticas, por ejemplo al buscar dentro de las bases de datos de estructuras moleculares, que pueden ser representadas como grafos (ver Karen Márquez, 33: Ha empleado tecnología cognitiva, inteligencia artificial y 'big data' para personalizar el aprendizaje infantil). Pero existen soluciones alte ativas a tener que resolver el problema en todas sus formas posibles, como el algoritmo de Babai.
Datos encriptados en peligro
Un avance similar a lo que afirma Babai sobre un problema de una complejidad computacional similar al isomorfismo de grafos tendría unas repercusiones más importantes. Conocido como la factorización – la descomposición de un número en todos sus factores – representa la encriptación más extendida para asegurar datos almacenados e informaciones que se desplacen por inte et.
El mejor algoritmo conocido para la factorización actualmente se encuentra en una clase de dificultad similar a la que ha acogido durante tanto tiempo el isomorfismo de grafos. La factorización carece de algunas características matemáticas que el resultado de Babai podría empezar a permitir. Lipton afirma que se trata de un recordatorio de que nuevos algoritmos pueden revocar las ortodoxias bien arraigadas sobre este tipo de problemas.
"Si alguien averigua cómo hacer que eso se acelere, incluso de forma teórica, sería muy preocupante a los criptógrafos", explica. La encriptación existente puede romperse mediante el uso de una importante potencia computacional si los números empleados para sembrar los algoritmos de encriptación no fueron lo suficientemente grandes. Un avance algorítmico para la factorización podría cambiar lo que resulta práctico para las agencias gube amentales con acceso a una importante potencia computacional.
Incluso si no resultara práctico un mejor algoritmo para la factorización, sería motivo para un examen de consciencia, dice Lipton. "Resultaría más difícil ponerse delante de un público y afirmar: 'Mi encriptación es segura porque emplea la factorización".