“El problema de esta compañía es la falta de cultura innovadora”, dijo el CEO mientras pedía a su secretaria que le imprimiese los correos electrónicos del día para revisarlos y sacaba su pluma del bolsillo para firmar las actas de una reunión…

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.

El pasado 4 de enero, László Babai, impactaba a la comunidad tras retractarse de un resultado que, en noviembre de 2015, los expertos de la disciplina habían aclamado como el logro de la década. Poco después, el 9 de enero, Babai anunciaba que había corregido el error presente en su demostración. Y cinco días más tarde, el matemático que había identificado el problema en el trabajo de Babai confirmaba públicamente que la nueva demostración de Babai era correcta.