Fraternitatea problemelor care încurcă computerele a pierdut un membru proeminent. Informaticianul László Babai a prezentat anul acesta un nou algoritm care abordează eficient problema izomorfismului grafic. Este un tip de problemă pe care computerele se străduiesc să o rezolve, chiar dacă o soluție furnizată în prealabil este ușor de verificat. Presupunând că este confirmat, spune informaticianul teoretic de la Stanford, Ryan Williams, acesta este cel mai mare progres în domeniu din mai bine de un deceniu.
Problema necesită ca computerele să compare două grafice sau rețele de puncte conectate și să determine dacă toate punctele sunt legate în același mod. Anterior, timpul necesar pentru rezolvarea problemei a crescut aproape exponențial cu dimensiunea graficului. Algoritmul lui Babai, născut din decenii de efort matematic, ține sub control timpul necesar de calcul prin rezolvarea chiar și a celor mai dificile cazuri în ceea ce se numește timp cvasipolinomial (SN: 12/12/15, str. 6). Dovada lui Babai poate oferi perspective pentru factorizarea numerelor mari și rezolvarea altor probleme cu statut ușor de verificat și greu de rezolvat.