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

Plutón: la enorme complejidad de un planeta enano

Parece que fue ayer cuando la sonda New Horizons pasó por Plutón mostrándonos el verdadero rostro de un objeto del cinturón de Kuiper por primera vez. Pero ya han pasado unos ocho meses y en este tiempo el equipo de la misión ha podido analizar los datos de la sonda con más calma y publicar varios artículos científicos. Los últimos, aparecidos en la revista Science, nos muestran un mundo pequeño, pero increíblemente complejo.

link:
 Plutón: la enorme complejidad de un planeta enano