Une introduction à la complexité de Kolmogorov et une application à l’algorithmique

Cet exposé se fera en deux parties. Dans un premier temps on présentera la notion de complexité de Kolmogorov. Cette dernière, introduite par Chaitin et Kolmogorov dans les années 1960, permet de mesure la quantité d’information contenue dans un objet fini discret (graphe, chaîne de caractères, etc), et peut être vue comme une version algorithmique de l’entropie à la Shannon. On discutera de ses principales propriétés. La seconde partie de l’exposé sera consacrée à un exemple d’application de la complexité de Kolmogorov à travers un récent résultat fondamental de Möser, qui a donné une preuve constructive du lemme local de Lovasz (un théorème central en combinatoire), présenté sous forme de problème de satisfaction de contraintes. Cette preuve est “constructive” dans la mesure où elle fait intervenir un algorithme probabiliste pour résoudre le problème de satisfaction de contraintes associé. L’algorithme en question est extrêmement concis, voire presque trivial, mais la preuve de sa correction est a priori difficile. Cependant, comme l’a montré Möser, cette preuve se trouve elle-même grandement simplifiée par l’utilisation de la complexité de Kolmogorov.