Complexité de Kolmogorov

En informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, , chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff. Cette quantité peut être vue comme une évaluation d'une forme de complexité de l'objet. Considérons deux textes, chacun composé d'une chaîne de 32 caractères : abababababababababababababababab et 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7 Le premier de ces deux textes peut être engendré par l'algorithme « ab » autrement dit par un algorithme de , alors que le second ne semble pas avoir de petit algorithme qui l'engendre mise à part l'algorithme qui consiste à écrire cette chaîne de caractères, c'est-à-dire un algorithme de . Ainsi, le premier texte semble avoir une complexité de Kolmogorov plus petite que celle du deuxième. vignette|L'ensemble de Mandelbrot. La figure de droite montre une qui présente l'ensemble de Mandelbrot. Cette image de de palette pèse environ . Par contre, un petit algorithme peut reproduire cette image à partir de la définition mathématique de l'ensemble de Mandelbrot et des coordonnées des coins de l'image. Ainsi, la complexité de Kolmogorov de l'image bitmap (non compressée) est beaucoup moins que dans un modèle de calcul raisonnable. Considérons une machine informatique M pouvant exécuter des programmes. On dit que cette machine est universelle lorsqu’elle peut émuler n'importe quelle autre machine informatique. La machine de Turing universelle en est un exemple. On note P l'ensemble des programmes écrits pour la machine M. Pour un programme p ∈ P, on note l(p) sa longueur en nombre d’instructions pour la machine M et s(p) sa sortie.