La complexité
algorithmique (complexité de calcul, ou la complexité de Kolmogorov), est une
idée fondamentale dans la théorie de la complexité algorithmique et 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 étant le programme le plus
court et le plus efficace qui peut produire la chaîne. Bien qu'il existe un
nombre infini de programmes qui peuvent produire une chaîne donnée, un
programme ou groupe de programmes sera toujours la plus courte. Il n'existe
aucun moyen algorithmique de trouver l'algorithme de plus court qui délivre en
sortie une chaîne donnée, ce qui est l'un des premiers résultats de la théorie
de la complexité de calcul. Même ainsi, nous pouvons faire une supposition
éclairée. Ce résultat, (la complexité de calcul d'une chaîne), s'avère être
très important pour les épreuves liées à la calculabilité.
Depuis n'importe
quel objet physique ou les biens peuvent en principe être décrits à la
quasi-épuisement par une chaîne de bits, des objets et des propriétés peuvent
être considérés comme ayant complexité algorithmique ainsi. En fait, la
réduction de 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 autour de nous ont tendance à provenir de trois principaux
processus de production; émergence, l'évolution et l'intelligence, avec les
objets produits par chaque tendant vers une plus grande complexité
algorithmique.
La complexité de
calcul est une notion fréquemment utilisée en théorie de l'informatique pour
déterminer la difficulté relative de calcul des solutions à larges classes de
problèmes mathématiques et logiques. Plus de 400 classes de complexité
existent, et des classes supplémentaires sont constamment découvertes. Le
célèbre P = NP question concerne la nature de deux de ces classes de
complexité. Classes de complexité incluent des problèmes beaucoup plus
difficile que tout ce que l'on pourrait affronter en mathématiques jusqu'à
calcul. Il y a beaucoup de problèmes imaginables dans la théorie de la
complexité algorithmique qui exigeraient une quantité quasi-infinie de temps à
résoudre.
La complexité
algorithmique et de concepts connexes ont été développés dans les années 1960
par des dizaines de chercheurs. Andrey Kolmogorov, Ray Solomonoff et Gregory
Chaitin ont apporté des contributions importantes à la fin des années 60 avec
le algorithmique théorie de l’information. Le principe de la longueur minimale
du message, étroitement liée à la complexité algorithmique, fournit une grande
partie de la base de statistiques et l'inférence inductive et l'apprentissage
de la machine.