Complexité - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en sciences de l’information. La définition connaît des nuances importantes selon ces différents domaines.
La complexité du point de vue de la théorie de l’information
Une notion de complexité est définie en Théorie algorithmique de l'information.
Complexité de Kolmogorov
La théorie de la complexité de Kolmogorov définit la complexité d’un objet fini par la taille du plus petit programme informatique (au sens théorique) qui permet de produire cet objet. Ainsi, un texte compressible a une faible complexité et contient peu d’information. C’est d’ailleurs pourquoi les utilitaires de compression généralistes ne peuvent pas comprimer des fichiers totalement aléatoires (opération par nature impossible), mais uniquement des fichiers dont on sait à l’avance qu’ils comportent une certaine redondance qui se traduit par des corrélations.
La complexité de Kolmogorov est un sujet discuté. On peut en effet toujours donner à un ordinateur une construction telle qu’une opération très particulière (par exemple le calcul de pi ou l’impression de l’intégrale des œuvres de Victor Hugo) y sera codée par un bit. On retrouve ici la notion connue qu’une information n’est jamais contenue dans un message seul, mais toujours dans le couple message + décodeur pris de façon indissociable. Aussi la notion de « plus petit programme théorique » ne peut-elle être définie opérationnellement de façon rigoureuse et univoque qu'avec la référence à une machine. On pourrait objecter qu’il suffit de prendre comme référence la machine la plus simple. C’est oublier que ce que nous nommerons simple dépend justement de notre vécu et de notre langage, tous deux arbitraires. Voir les articles Rasoir d'Occam et Paradoxe du compresseur : The library is the language ( « La bibliothèque est le langage »).
Une difficulté supplémentaire réside dans le fait que la complexité de Kolmogorov n'est pas 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 nombres transcendants comme π, e ou 0,12345678910111213… dont le développement binaire est infini mais la suite des décimales parfaitement calculable. En revanche, le nombre dit Ω 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 dense dans R, 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 peut démontrer que tous les nombres incompressibles sont normaux, la suite de leurs décimales doit être aléatoire au sens fort, au moins à partir d'un certain rang.
Complexité algorithmique
La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Elle définit plusieurs classes de complexité (P, NP, ...) permettant de classer les algorithmes selon leurs caractéristiques.
Autres complexités
- Système complexe.
