Qu'est-ce que la complexité algorithmique?

La complexité algorithmique (complexité de calcul, ou complexité de Kolmogorov) est une idée fondamentale de la théorie de la complexité de calcul et de la théorie de l'information algorithmique , et joue un rôle important dans l'induction formelle.

La complexité algorithmique d'une chaîne binaire est définie comme étant le programme le plus court et le plus efficace pouvant produire la chaîne. Bien qu'il existe un nombre infini de programmes pouvant produire une chaîne donnée, un programme ou un groupe de programmes sera toujours le plus court. Il n'y a pas de moyen algorithmique de trouver l'algorithme le plus court qui génère une chaîne donnée; c'est l'un des premiers résultats de la théorie de la complexité computationnelle. Même dans ce cas, nous pouvons faire une supposition éclairée. Ce résultat (la complexité de calcul d'une chaîne) s'avère très important pour les preuves relatives à la calculabilité.

Comme tout objet ou propriété physique peut en principe être décrit comme une quasi-épuisement par une chaîne de bits, on peut dire que les objets et les propriétés ont également une complexité algorithmique. En fait, réduire la complexité des objets du monde réel aux programmes qui les produisent en sortie est une façon de voir l’entreprise de la science. Les objets complexes qui nous entourent ont tendance à provenir de trois processus générateurs principaux; émergence , évolution et intelligence , les objets produits par chacun tendant à une plus grande complexité algorithmique.

La complexité informatique est une notion fréquemment utilisée en informatique théorique pour déterminer la difficulté relative du calcul des solutions à de vastes classes de problèmes mathématiques et logiques. Il existe plus de 400 classes de complexité et de nouvelles classes sont continuellement découvertes. La fameuse question P = NP concerne la nature de deux de ces classes de complexité. Les classes de complexité comportent des problèmes bien plus difficiles que tout ce que l'on peut affronter en mathématiques jusqu'au calcul. Il existe de nombreux problèmes imaginables dans la théorie de la complexité informatique qui nécessiteraient un temps de traitement quasi infini.

La complexité algorithmique et les concepts associés ont été développés dans les années 1960 par des dizaines de chercheurs. Andrey Kolmogorov, Ray Solomonoff et Gregory Chaitin ont apporté d'importantes contributions à la fin des années 60 avec la théorie algorithmique de l'information. Le principe de longueur minimale de message, étroitement lié à la complexité algorithmique, fournit en grande partie le fondement de l'inférence statistique et inductive et de l'apprentissage automatique.