Cultura y divulgación
10 meneos
68 clics

Un resultado importante sobre el problema de isomorfismo de grafos [ENG]

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.

| etiquetas: isomorfismo , grafos , complejidad computacional

menéame