La complejidad del isomorfismo de grafos es cuasipolinómica en tiempo

László Babai (Premio Knuth 2015) afirmó en diciembre de 2015 haber demostrado que la complejidad algorítmica del problema del isomorfismo de grafos es cuasipolinómica (LCMF, 11 Dic 2015). El matemático peruano Harald A. Helfgott ha verificado la demostración en detalle y afirma que es correcta. El 14 de enero impartió una charla Bourbaki en el Instituto Henri Poincaré de París. La importancia del trabajo de Babai (65 años), es que abre la esperanza a que matemáticos más jóvenes, usando sus nuevas ideas, logren avances relevantes sobre el problema P vs NP. El isomorfismo de grafos es un problema NP, que no sabemos si es NP-completo; si estuviera en P sería algo revolucionario.

link:
 La complejidad del isomorfismo de grafos es cuasipolinómica en tiempo