KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

La théorie de la complexité de Kolmogorov d'une suite numérique S est définie comme la taille, K(S), du plus court programme P qui, confié à une machine universelle (tout ordinateur contemporain en est une), produit la suite S. Cette notion est séduisante car elle synthétise en un seul nombre plusieurs mesures de complexité dont celle que propose la théorie de l'information de l'Américain Claude Shannon (1916-2001), dont elle est la généralisation. Le revers de la médaille de cette généralité de la complexité de Kolmogorov est son lien avec les théorèmes d'incomplétude de l'Austro-Américain Kurt Gödel (1906-1978). En particulier, ce lien a pour conséquence qu'il ne peut exister aucun mécanisme général de calcul pour déterminer sans erreur K(S) pour toute séquence S. On croyait donc que ce qui est la plus générale des mesures de complexité ne pourrait pas trouver à s'appliquer concrètement et resterait seulement un outil mathématique pour envisager, dans l'abstrait, les concepts d'information et de complexité, sans impact d'aucune sorte dans aucune discipline.

Une série de travaux viennent d'établir que ce n'est pas le cas et que la notion abstraite conduit à des applications à l'utilité incontestable. La méthode suivie repose sur l'utilisation des algorithmes de compression de données qui sont devenus centraux pour nombre d'applications informatiques en même temps qu'ils sont devenus efficaces. On peut les voir comme des outils de recherche de régularités dans les séquences numériques – les fichiers informatiques – et leur exploitation pour transformer un fichier F en un fichier compressé C(F), ce qui peut être vu comme un calcul approché de K(S). Le savoir-faire accumulé depuis plus de trente ans dans ces algorithmes de compression de données a pour conséquence que la valeur approchée qu'ils évaluent de K(S) est dans bien des cas assez précise. Cela a conduit à des méthodes de classification automatique : on évalue la complexité de Kolmogorov relative d'une séquence S par rapport à une autre S', ce qui permet de classer automatiquement les séquences d'un ensemble fixé à l'avance de séquences S. Cette technique a été appliquée par une équipe de chercheurs de l'université d'Amsterdam conduite par Paul Vitanyi. Avec des séquences génétiques, elle a produit des arbres phylogénétiques jugés convenables. La méthode a aussi été mise en œuvre pour déterminer un arbre des langues indo-européennes, pour classer des morceaux de musiques et des textes. En 2008, Sihem Belabbes du British Institute of Technology and E-commerce et Gilles Richard de l'Institut de recherche en informatique de Toulouse ont utilisé la complexité de Kolmogorov pour élaborer un nouveau type d'algorithmes de détection des pourriels, ces courriers électroniques publicitaires qu'on cherche à filtrer pour qu'ils n'encombrent pas les boîtes à lettres électroniques (S. Belabbes et G. Richard, « On Using SVM and Kolmogorov Complexity for Spam Filtering », in Proceedings of the Twenty-First International Florida Artificial Intelligence Research Society Conference, 15-17, mai 2008).

— Jean-Paul DELAHAYE