La complexité algorithmique (complexité computationnelle ou complexité de Kolmogorov) est une idée fondamentale à la fois de la théorie de la complexité computationnelle et de la théorie algorithmique de l’information, et joue un rôle important dans l’induction formelle.
La complexité algorithmique d’une chaîne binaire est définie comme 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’existe aucun 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 ainsi, 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 liées à la calculabilité.
Étant donné que tout objet ou propriété physique peut en principe être décrit jusqu’à l’épuisement par une chaîne de bits, on peut également dire que les objets et les propriétés ont une complexité algorithmique. En fait, réduire la complexité des objets du monde réel à des programmes qui produisent les objets 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 vers une plus grande complexité algorithmique.
La complexité computationnelle est une notion fréquemment utilisée en informatique théorique pour déterminer la difficulté relative de calculer les solutions à de larges classes de problèmes mathématiques et logiques. Il existe plus de 400 classes de complexité et des classes supplémentaires sont continuellement découvertes. La fameuse question P = NP concerne la nature de deux de ces classes de complexité. Les classes de complexité comprennent des problèmes bien plus difficiles que tout ce que l’on pourrait affronter en mathématiques jusqu’au calcul. Il existe de nombreux problèmes imaginables dans la théorie de la complexité computationnelle qui nécessiteraient un temps presque infini pour être résolus.
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 la longueur minimale du message, étroitement lié à la complexité algorithmique, fournit une grande partie de la base de l’inférence statistique et inductive et de l’apprentissage automatique.