Tag Archives:: Isomorfismo de grafos

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 […]

El famoso László Babai (Premio Knuth 2015) afirma haber demostrado que la complejidad algorítmica del problema del isomorfismo de grafos es cuasipolinómica. Catedrático de la Universidad de Chicago, EEUU, ha impartido una charla en su propia universidad para explicar su demostración, basada en combinar la teoría de grupos y la combinatoria. El vídeo de la charla permite hacerse una […]