Andreï Kolmogorov est l’un des plus grands mathématiciens que le genre humain ait produit au XXème siècle. Formé à l’école soviétique, il était convaincu qu’aucun théorème, conjecture et autre "bizarrerie" mathématique ne saurait lui résister et qu’il saurait le démontrer. C’est ce qu’il fera par exemple, avec le 13 ème problème de Hilbert en 1957.
Né au début du XXème siècle à Tambor (Union Soviétique), Andreï Kolmogorov nous intéresse particulièrement car son nom est associé à la notion de complexité des objets, qui servira de base à de nombreux travaux en mathématiques, en sécurité du TI, en cryptographie, etc.
Le personnage est extraordinaire et témoigne de la qualité des enseignements délivrés dans le monde soviétique de l’époque et dans ce que l’on appelait l’Europe de l’Est, constituée des états fédérés par l’ours de Moscou : Roumanie, Tchécoslovaquie, Yougoslavie, etc.
Et il n’y a rien d’étonnant à ce que de nombreux algorithmes portent aujourd’hui le nom de mathématiciens issus de ces communautés et nous aient accompagné tout au long de nos études.
Kolmogorov est attaché à une nouvelle conception de l’information et à la complexité depuis les années 70. Auteur boulimique, il a publié plus de 500 documents de toutes sortes, livres et communications scientifiques dans de nombreux domaines : transformée de Fourier, probabilités, géométrie, etc, mais aussi complexité algorithmique, bien qu’il ne faille pas confondre complexité de Kolmogorov avec celle des algorithmes.
Si Andreï Kolmogorov n’a pas eu le prix Nobel, ni le prix Turing, c’est à la fois parce qu’il était soviétique et qu’il rodait comme une sorte d’incompréhension entre les blocs de l’est et ceux du monde occidental, mais aussi parce qu’il était un mathématicien pur et d’une certaine manière éloigné des préoccupations des systèmes d’information, là encore à ne pas confondre avec l’information elle-même.
La complexité de Kolmogorov est attachée à un objet et pas à un algorithme. L’objet pouvant être un nombre, une image, une chaîne de caractères. Il s’agit de la taille du plus petit algorithme qui permet de générer cet objet, en fait la taille du programme de génération, exprimé en nombre de caractères déterminé pour un langage donné.
Wikipedia nous en fournit un exemple significatif, celui de 2 chaînes de 32 caractères :
abababababababababababababababab
et 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7
Le premier de ces deux textes peut être fabriqué par l'algorithme "ab 16 fois", autrement dit par un algorithme de 10 caractères, alors que le second ne semble pas pouvoir être produit par autre chose qu’une simple recopie, le plus petit algorithme qui l'engendre. Soit 32 caractères.
Au sens de Kolmogorov, le premier texte semble avoir une complexité de Kolmogorov plus petite que celle du deuxième. On dit bien "semble", car la complexité de Kolmogorov ne peut pas être calculée.
La taille de l’algorithme est une chose, mais la complexité de Kolmogorov en est une autre. C’est la taille du plus petit algorithme pour générer la chaîne, qui peut-être n’a pas encore été découvert.
Si on part d’un objet S, on ne peut donc pas calculer K(S), la complexité de Kolmogorov. Il n’existe pas d’algorithme pour effectuer ce travail. Mais plus cette complexité sera élevée, plus il sera difficile de prévoir l’objet cible, ce qui sera particulièrement intéressant en cryptographie avec l’intrusion des machines quantiques.
Pendant longtemps, le concept a été considéré comme ne pouvant pas être réutilisé concrètement et n’ayant pas d’applications concrètes.
En fait, il n’en a rien été et on l’a exploité dans des domaines tels que la recherche de régularités dans un fichier, dans la compression des données, dans la classification des langues, de textes et de musiques, la détection de pourriels et donc en cryptographie.
Le nom d’Andreï Kolmogorov ne peut pas être dissocié de ceux d’autres grands mathématiciens soviétiques : Gregory Chaitin, Per Martin-Löf, Leonard Levin, mais surtout Alexandre Aleksandrov, dont il a partagé la vie pendant 53 ans et sans lequel il n’aurait probablement pas été le fabuleux scientifique que nous connaissons.