Mathématicien russe, lauréat du prix Nevanlinna en 1990 pour ses travaux sur la théorie de la complexité. Né le 16 février 1963 à Belovo (Russie), Alexander Alexandrovitch Razborov est le fils de deux ingénieurs électriciens ; il fait ses études supérieures à l'université de Moscou, puis soutient en 1987 sa thèse de doctorat à l'institut de mathématiques Steklov à Moscou ; c'est dans cet institut qu'il continue de faire ses recherches en mathématiques et en informatique théorique.
Les contributions majeures de Razborov à l'élucidation du problème central en théorie de la complexité, à savoir le nombre de pas et la quantité de mémoire nécessaires au calcul d'une fonction, sont nombreuses. En 1985, encore étudiant, il parvient à établir un résultat marquant sur l'existence d'algorithmes polynomiaux en temps pour une tâche qui semble non polynomiale. La technique développée par Razborov pour analyser les performances d'un circuit booléen – un circuit dont les portes représentent des fonctions logiques telles que « ou », « et », « non » ... – lui permet de montrer que le nombre de portes d'un circuit ne contenant pas la fonction « non » doit être superpolynomial pour qu'on puisse tester qu'un graphe contient un sous-graphe complet d'une taille donnée.
Razborov a reçu le prix Gödel, qui récompense des travaux en informatique théorique, en 2007.
Bernard PIRE
Retour en haut
