Voir la source de Complexité de Kolmogorov

{{Autre4|complexité de Kolmogorov|une autre mesure de complexité|complexité de Lempel-Ziv}}
{{à recycler|date=juillet 2013|thème=informatique}}
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, [[image numérique]], [[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<ref>{{article|lien auteur=Andrey Kolmogorov|prénom=Andrey|nom=Kolmogorov|année=1963|titre=On Tables of Random Numbers|journal=Sankhyā Ser. A.|volume=25|pages=369–375|mr=178484}}</ref>{{,}}<ref>{{article|lien auteur=Andrey Kolmogorov|prénom=Andrey|nom=Kolmogorov|année=1998|titre=On Tables of Random Numbers|journal=Theoretical Computer Science|volume=207|numéro=2|pages=387–395|doi=10.1016/S0304-3975(98)00075-9|mr=1643414}}</ref>. Elle est aussi parfois nommée ''complexité de Kolmogorov-[[Ray Solomonoff|Solomonoff]]''{{Référence nécessaire|date=28 janvier 2019}}{{Par qui}}. Cette quantité peut être vue comme une évaluation d'une forme de [[complexité]] de l'objet.

== Exemples ==

=== Premier exemple - chaînes de texte ===
Considérons deux textes, chacun composé d'une chaîne de 32 caractères :

: <code>abababababababababababababababab</code>
:  et <code>4c1j5b2p0cv4w1x8rx2y39umgw5q85s7</code>

Le premier de ces deux textes peut être engendré par l'algorithme « <code>ab</code> {{nb|16 fois}} » autrement dit par un algorithme de {{nb|10 caractères}}, 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 {{nb|32 caractères}}. Ainsi, le premier texte semble avoir une complexité de Kolmogorov plus petite que celle du deuxième.

[[Fichier:Mandelpart2 red.png|vignette|L'ensemble de Mandelbrot.]]

=== Deuxième exemple : une image ===
La figure montre une [[image bitmap]] qui présente l'[[ensemble de Mandelbrot]]. Cette image de {{nb|24 bits}} de palette pèse environ {{nb|1,7|mégaoctets (Mo)}}<ref>[https://commons.wikimedia.org/wiki/File:Mandelpart2_red.png?uselang=fr Page de description du fichier] sur [[Wikimedia Commons]].</ref>. 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 {{nb|1,7|mégaoctets}} dans un modèle de calcul raisonnable.

== Définition ==
Considérons une machine informatique {{mvar|M}} pouvant exécuter des programmes. On dit que cette machine est universelle lorsqu’elle peut [[Émulation|émuler]] n'importe quelle autre machine informatique. La [[machine de Turing universelle]] en est un exemple.

On note {{mvar|P{{ind|M}}}} l'ensemble des programmes écrits pour la machine {{mvar|M}}. Pour un programme {{math|''p'' ∈ ''P{{ind|M}}''}}, on note {{math|''l''(''p'')}} sa longueur en nombre d’instructions pour la machine {{mvar|M}} et {{math|''s''(''p'')}} sa sortie. La complexité de Kolmogorov {{math|''K{{ind|M}}''(''x'')}}, ou complexité algorithmique, d’une [[Suite (mathématiques)|suite]] {{mvar|x}} finie de caractères pour une machine {{mvar|M}} est déﬁnie par :
: <math>K_M (x) = \min_{p\in P_M} \{l(p), s(p) = x\}</math>.
C’est donc la longueur du plus petit programme écrit pour la machine {{mvar|M}} qui génère la suite {{mvar|x}}. Une suite constante a une complexité faible car les programmes qui la génèrent peuvent être très courts.

Reste à savoir dans quelle mesure la fonction {{math|''K{{ind|M}}''(''x'')}} dépend de la machine {{mvar|M}}, car on peut tout à fait imaginer une machine possédant des instructions simples pour générer certaines suites complexes. La réponse est la suivante : il existe une machine universelle {{mvar|U}} (souvent qualifiée d'additivement optimale) telle que pour toute machine {{mvar|M}} il existe une constante {{math|''c{{ind|M}}''}} vérifiant pour toute suite {{mvar|x}} l'inégalité :
: <math> K_U(x) \leq K_M(x) + c_M </math>
Intuitivement, {{math|''c{{ind|M}}''}} est la longueur d'un [[interpréteur]] (ou d'un [[émulateur]]), écrit pour la machine {{mvar|U}}, du langage utilisé par la machine {{mvar|M}}. On parle alors d’universalité de la complexité de Kolmogorov, en ce sens qu'elle ne dépend pas, à une constante additive près, de la machine considérée. 

Une suite peut alors être considérée comme d’autant plus « aléatoire » que sa complexité est grande par rapport à sa taille. De ce point de vue, les décimales des nombres {{math|π}}, {{math|e}} ou {{racine|2}} ne sont pas vraiment aléatoires puisqu'il existe des algorithmes très simples pour les calculer.

Une difficulté supplémentaire réside dans le fait que la complexité de Kolmogorov n'est pas [[Indécidabilité|décidable]] : on peut donner un algorithme produisant l'objet voulu, ce qui prouve que la complexité de cet objet est au plus la taille de cet algorithme. Mais on ne peut pas écrire de programme qui donne la complexité de Kolmogorov de tout objet que l'on voudrait lui donner en entrée.

La notion, manipulée avec précaution, se révèle néanmoins à l'origine de nombreux résultats théoriques.

Par exemple, on appelle nombre ''incompressible'' au sens de Kolmogorov un réel dont le développement p-adique (binaire pour plus de commodité) est comparable à la taille de l'algorithme qui permet de le calculer. En ce sens, tous les rationnels et certains irrationnels sont compressibles, en particulier les [[Nombre transcendant|nombres transcendants]] comme [[Pi|{{math|π}}]], [[e (nombre)|{{math|e}}]], les [[Nombre de Liouville|nombres de Liouville]] ou [[Constante de Champernowne|0,12345678910111213…]] dont le développement binaire est infini mais la suite des décimales parfaitement calculable. En revanche, le nombre dit [[Oméga de Chaitin|{{math|Ω}} de Chaitin]] ne l'est pas : ce nombre mesure la probabilité qu'une machine, alimentée par un programme composé de bits aléatoires, s'arrête. La topologie des nombres incompressibles est intéressante : on conçoit intuitivement que cet ensemble est [[Partie dense|dense]] dans <math>\mathbb R</math>, mais il est impossible d'exhiber de façon [[algorithmique]] un réel incompressible, puisque cela reviendrait à en donner une méthode de calcul efficace. De plus, on peut démontrer que tous les nombres incompressibles sont [[Nombre normal|normaux]], la suite de leurs décimales doit être aléatoire au sens fort.

== Propriétés ==
La complexité de Kolmogorov n'est pas [[Calculabilité|calculable]].
En d'autre termes il n'existe pas de programme informatique qui prenne en entrée ''s'' et renvoie ''K''(''s''). Pour le prouver, raisonnons par l'absurde et supposons qu'une telle fonction ''Kolmo'' existe. On note k la taille de cette fonction (i.e. le nombre de caractères de son [[code source]]). On pourrait alors écrire l'algorithme suivant :

   ''n'' := 1
   '''Tant que''' ''Kolmo(n) < k + 100'' '''faire''':
     ''n := n + 1''
   '''Fin du Tant que'''
   '''écrire''' ''n''

Ainsi cet algorithme écrit le plus petit nombre à avoir une complexité de Kolmogorov supérieure à k+100 (ce nombre existe nécessairement car il n'y a qu'un nombre fini de programmes de taille plus petite que k+100 et il y a une infinité de nombres [[Entier naturel|entiers naturels]]). 

Mais l'algorithme ci-dessus s'écrit justement avec moins de k+100 caractères : il est donc de complexité inférieure à k+100, or il écrit justement un nombre de complexité supérieure à k+100, ce qui est absurde (on peut rapprocher cette remarque de l'argument utilisé pour le [[paradoxe de Berry]]). 

Donc il n'existe pas de fonction qui calcule la complexité de Kolmogorov.

== Variantes avec ressources bornées ==
La définition de la complexité de Kolmogorov est défini en fonction du plus petit programme qui produit x. Mais ce programme pourrait consommer d'importantes ressources. C'est pourquoi il est important de prendre en compte les ressources utilisées par le programme<ref>{{ouvrage |langue=en-gb | prénom=Osamu | nom=Watanabe | titre=Kolmogorov Complexity and Computational Complexity | collection=EATCS Monographs on Theoretical Computer Science | date=1992 |doi=10.1007/978-3-642-77735-6 |isbn=978-3-642-77737-0| lire en ligne=https://link.springer.com/book/10.1007/978-3-642-77735-6 |consulté le=2019-07-14 }}</ref>. Soit U une machine universelle. Voici une version bornée par le temps t :

<math> C^t(x) = \min_{p} \{|p| : U(p) \text{ écrit } x \text{ en } t(|x|) \text{ étapes}\} </math>

On notera que la complexité temporelle est définie en fonction de la sortie x et non pas de la taille du programme p. Sipser, en 1983<ref>{{Article |prénom1=Michael |nom1=Sipser |titre=A Complexity Theoretic Approach to Randomness |périodique=Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing |série=STOC '83 |éditeur=ACM |date=1983 |isbn=9780897910996 |doi=10.1145/800061.808762 |lire en ligne=http://doi.acm.org/10.1145/800061.808762 |consulté le=2019-07-14 |pages=330–335 }}</ref>, a proposé une mesure de la taille du plus petit programme qui permet de distinguer une chaîne de caractère x. Buhrman, Fortnow et Laplante en 2002 en donnèrent une version non déterministe, en prenant une machine universelle non-déterministe<ref>{{Article |prénom1=H. |nom1=Buhrman |prénom2=L. |nom2=Fortnow |prénom3=S. |nom3=Laplante |titre=Resource-Bounded Kolmogorov Complexity Revisited |périodique=SIAM Journal on Computing |volume=31 |numéro=3 |date=2001-01-01 |issn=0097-5397 |doi=10.1137/S009753979834388X |lire en ligne=https://epubs.siam.org/doi/10.1137/S009753979834388X |consulté le=2019-07-14 |pages=887–905 }}</ref>. On trouve d'autres définitions chez Levin{{Référence nécessaire|date=14 juillet 2019}}, et chez Allender<ref>{{Article |prénom1=Eric |nom1=Allender |titre=When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity |périodique=Of Reductions,in“proc.29thacm Symposium on Theory of Computing |date=1997 |lire en ligne=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.4621 |consulté le=2019-07-14 |pages=730–738 }}</ref> où la définition de la complexité est la somme de la complexité de Kolmogorov et la contribution de la complexité temporelle.  

== Lien avec la théorie de la complexité algorithmique ==
Des liens entre complexité de Kolmogorov et [[Théorie de la complexité (informatique théorique)|théorie de la complexité]] ont établi en utilisant l'ensemble suivant comme [[Oracle (machine de Turing)|oracle]] :

R = ensemble des chaînes de caractères x dont la complexité de Kolmogorov est au moins |x|/2

En 2002, Allender, Buhrman, Koucky, van Melkebeek et Ronnerbuger<ref name=":0">{{Article |prénom1=E. |nom1=Allender |prénom2=H. |nom2=Buhrman |prénom3=M. |nom3=Koucky |prénom4=D. van |nom4=Melkebeek |titre=Power from random strings |périodique=The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. |date=2002-11 |doi=10.1109/SFCS.2002.1181992 |lire en ligne=https://ieeexplore.ieee.org/document/1181992/ |consulté le=2019-07-14 |pages=669–678 }}</ref>  démontrent que [[PSPACE]] est inclus dans P<sup>R</sup> et que [[EXPTIME]] est inclus dans NP<sup>R</sup>. Puis, en 2004, Allender, Buhrman, Koucky démontrent<ref>{{Article |langue=en |prénom1=Eric |nom1=Allender |prénom2=Harry |nom2=Buhrman |prénom3=Michal |nom3=Koucký |titre=What Can be Efficiently Reduced to the K-Random Strings? |périodique=STACS 2004 |série=Lecture Notes in Computer Science |éditeur=Springer Berlin Heidelberg |date=2004 |isbn=9783540247494 |doi=10.1007/978-3-540-24749-4_51 |lire en ligne=https://link.springer.com/chapter/10.1007/978-3-540-24749-4_51 |consulté le=2019-07-14 |pages=584–595 }}</ref>, en utilisant les mêmes techniques, que [[NEXPTIME]] est inclus dans NP<sup>R</sup>.

== Notes et références ==
{{Crédit d'auteurs|externe|source=https://djalil.chafai.net/docs/Agreg/Manuel/agregation.pdf|titre=Petit manuel à l’usage des agrégatifs préparant l’oral de modélisation stochastique|GFDL=oui|auteur=Djèlil Chafaï|langue=fr|note=oui}}
{{Références}}

== Annexes ==
=== Bibliographie ===
* {{ouvrage|lang=fr|auteur1=[[Gregory Chaitin]]|titre=Hasard et complexité en mathématiques|sous-titre=la quête de Ω|éditeur=Flammarion|lieu=Paris|date=2009|isbn=978-2-0821-0568-2|bnf=cb41412252s|collection=Nouvelle bibliothèque scientifique|pages totales=236}}.
* {{ouvrage|auteur1=Ming Li|auteur2=Paul Vitanyi|lang=en|titre=An Introduction to Kolmogorov Complexity and Its Applications|éditeur=Springer Verlag|année=2008|isbn=978-0-387-49820-1|doi=10.1007/978-0-387-49820-1}}. 

=== Articles connexes ===
* [[Machine de Turing]]
* [[Théorie algorithmique de l'information]]
* [[Suite aléatoire]]
* [[Complexité de Lempel-Ziv]]

{{portail|Informatique théorique}}

[[Catégorie:Informatique théorique]]
[[Catégorie:Théorie algorithmique de l'information]]
[[Catégorie:Calculabilité]]