Qu'est-ce que la complexité algorithmique?

La complexité algorithmique (complexité informatique, ou complexité de Kolmogorov), est une idée fondamentale dans la théorie de la complexité computationnelle et

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 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 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 publie une chaîne donnée;Il s'agit de 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 très importante pour les preuves liées à la calculabilité. Étant donné que tout objet ou propriété physique peut être décrit en principe à proximité par une chaîne de bits, d'objets et de propriétéspeut également être considéré comme une complexité algorithmique.En fait, la réduction de la complexité des objets du monde réel aux programmes qui produisent les objets comme sortie, est un moyen de visualiser l'entreprise de science.Les objets complexes autour de nous ont tendance à provenir de trois processus de génération principaux; Émergence , Evolution et

intelligence

, avec les objets produits par chacun tendance à une plus grande complexité algorithmique. La complexité informatique est une notion fréquemment utilisée dans l'informatique théorique pour déterminer la difficulté relative de calculer les solutions à de larges classesdes problèmes mathématiques et logiques.Plus de 400 classes de complexité existent et des classes supplémentaires sont découvertes en continu.Le célèbre

P ' NP

Question concerne la nature de deux de ces classes de complexité.Les classes de complexité incluent des problèmes beaucoup plus difficiles que tout ce à quoi on pourrait confronter en mathématiques jusqu'au calcul.Il existe de nombreux problèmes imaginables dans la théorie de la complexité de calcul qui nécessiteraient un temps quasi infini pour résoudre.

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