Un algorithme quasipolynomial pour l'isomorphisme de graphes

**Un algorithme quasipolynomial pour l'isomorphisme de graphes,** **la contribution de László Babai fait grand bruit en informatique théorique** La théorie de la complexité, en informatique, classifie les problèmes selon leur difficulté intrinsèque, c'est-à-dire selon la complexité en temps de l'algorithme le plus efficace pour les résoudre. Par exemple, pour trier un tableau, il existe une multitude d'algorithmes: le tri par insertion, le tri par fusion, le tri par tas ou encore, le plus célèbre, le tri rapide. Les plus efficaces ont une complexité pseudolinéaire: pour trier éléments, il leur faudra opérations; d'autres algorithmes, comme le tri par insertion, ont une complexité quadratique: le nombre d'opérations évolue comme .