http://www.scottaaronson.com/blog/?p=2521
Rumores, rumores. Se dice que el informático László Babai en una conferencia el próximo martes explicará cómo se resuelve el problema del isomorfismo de grafos en tiempo cuasi polinómico. El mejor resultado hasta ahora (del mismo autor) era capaz de resolver el problema de saber si un grafo es isomorfo a otro en (e{\sqrt{n \log n}}), y ahora parece que lo tiene en (e{\text{polylog} n}), que es casi un tiempo polinómico.
Esto no arreglaría en nada la pregunta P!=NP, pero estaría al nivel del descubrimiento de que PRIMES es P.
Un poco de explicación:
Un grafo no es más que una colección de vértices y aristas (que conectan los vértices). Dos grafos son isomorfos si podemos reetiquetar los vértices de uno de manera que encaje perfecto con el otro (siempre y cuando se conserven las conexiones entre vértices, claro). Este problema lleva desde los 80 sin saberse si es NP o es P, y este resultado parece que lo situa muuy cerca de P.
Polylog es una función que crece un poco más rápido que el logaritmo pero no tanto como un polinomio. Es un poco técnico y hasta que no salga la conferencia y sus posteriores análisis no puedo dar más detalles (porque no los conozco, no porque sea un secreto xD), pero este es uno de los resultados en teoría de la computación más importantes de los últimos 10 años.
Aplicaciones tiene muchas por cierto para los fans del "y pa qué sirve esto". Desde saber si dos capturas de moléculas son de la misma molécula (aunque esté retorcida, girada, o entrelazada), hasta simplificación de problemas de logística o geociencias o lo que queráis. Compiladores, verificación de demostraciones por ordenador, pf, muchas cosas xD.
.
