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
No hay comentarios:
Publicar un comentario
Se bienvenido y comenta! recuerda, se respetuoso y no insultes o los comentarios seran eliminados.