László Babai es uno de los expertos mundiales en teoría de la complejidad computacional, especialmente en relación a grupos y grafos. Ganó recientemente el premio Knuth de 2015. Hoy queremos comentar un nuevo resultado que László ha anunciado situará el problema de isomorfimo de grafos casi en la clase de problemas que pueden resolverse en tiempo polinómico. Más exactamente László muestra que el problema de isomorfimo de grafos está dentro de la clase de problemas que pueden resolverse en tiempo cuasi-polinómico.
Comentarios
#0 Entradilla y titular en castellano.
Esto va a portada directamente!!
¿Otra vez con el P=NP?