Logique et ensemblesNotion · Glossaire
complexité de Bennett
À niveau de signification fixé, la complexité de Bennett, ou profondeur logique, d'un objet est le plus petit temps d'exécution parmi les programmes qui le produisent et dont la longueur ne dépasse la longueur minimale que d'une tolérance donnée. Elle distingue ainsi les objets rapidement reconstructibles de ceux dont toute description presque minimale exige un long calcul.
Sommaire
Ce que vous allez apprendre
- Définir la profondeur logique avec son niveau de signification.
- Refaire un exemple où le seuil modifie le temps minimal.
- Distinguer profondeur logique, complexité de Kolmogorov et complexité en temps.
En clair
Imaginez la suite de seize chiffres 0101010101010101. On peut la produire en recopiant tous ses chiffres, ou en donnant une courte consigne : répéter huit fois « 01 ». La première voie est immédiate mais longue à décrire ; la seconde est concise et demande plusieurs répétitions.
La profondeur logique s'intéresse au temps pris par les descriptions suffisamment courtes. Un objet est profond si même une bonne compression doit effectuer un calcul long pour le reconstruire. Être long ou désordonné ne suffit donc pas.
Définition
On fixe un langage de programmation universel et un objet fini x. La complexité de Kolmogorov K(x) est la longueur minimale d'un programme qui produit x puis s'arrête. Pour un seuil de tolérance s, appelé niveau de signification, on accepte les programmes dont la longueur ne dépasse pas K(x) + s.
Si t(p) désigne le temps d'exécution du programme p, la profondeur logique de x au seuil s est :
La machine universelle choisie est notée U, et |p| est la longueur du programme. Pour s = 0, seuls les programmes les plus courts concourent. Autoriser s > 0 évite qu'une différence minime de longueur impose artificiellement un programme extrêmement lent. La valeur numérique dépend de U et de s : la profondeur logique est donc toujours annoncée avec ces conventions.
Un exemple, pas à pas
Considérons un langage-jouet qui ne propose que deux façons de produire x = 0101010101010101. Le programme pcourt occupe 5 unités et répète « 01 » huit fois en 8 étapes. Le programme prapide contient les 16 chiffres et les affiche en 1 étape. Par définition du langage-jouet, aucun programme plus court n'existe : K(x) = 5.
1. Au seuil s = 0, la longueur autorisée vaut 5. Seul pcourt est admis.
2. Son exécution prend 8 étapes, donc D0(x) = 8.
3. Au seuil s = 11, la longueur autorisée vaut 5 + 11 = 16.
4. prapide devient admissible et donne D11(x) = 1.
2. Son exécution prend 8 étapes, donc D0(x) = 8.
3. Au seuil s = 11, la longueur autorisée vaut 5 + 11 = 16.
4. prapide devient admissible et donne D11(x) = 1.
Le contrôle est direct : 5 ≤ 5 pour le premier seuil, puis 16 ≤ 16 pour le second. Cet exemple illustre le rôle du seuil ; ses unités appartiennent au langage-jouet et ne donnent pas une profondeur absolue de la suite.
En pratique
En théorie de l'information algorithmique, la profondeur logique sépare deux questions : combien d'information irréductible contient un objet, et combien de calcul une description concise doit effectuer pour le produire. On examine K(x) pour la première, puis Ds(x) pour la seconde.
Pour comparer des structures engendrées par des calculs, on fixe d'abord la même machine universelle et le même seuil s. Sans ces conventions communes, comparer deux valeurs numériques de profondeur n'a pas de sens précis.
Pour reconnaître une organisation acquise au fil d'un long processus, on cherche une description courte dont la reconstruction reste lente. Une chaîne aléatoire simplement recopiée appelle plutôt la complexité de Kolmogorov : elle peut être incompressible sans être logiquement profonde.
À ne pas confondre
Complexité de Kolmogorov. Elle mesure la longueur de la description la plus courte, tandis que la profondeur logique mesure le temps des descriptions presque minimales. Dans l'exemple, K(x) = 5 unités et D0(x) = 8 étapes : les deux nombres répondent à des questions différentes.
Complexité en temps d'un algorithme. Elle étudie comment le coût d'un algorithme varie avec la taille de ses entrées. La profondeur logique part au contraire d'un objet fixé et compare les temps des programmes suffisamment courts qui le produisent.
Limites et pièges
Le seuil change le verdict. Dans le langage-jouet, passer de s = 0 à s = 11 fait tomber la profondeur de 8 à 1 étape. Il faut donc toujours préciser le niveau de signification utilisé.
La machine n'est pas neutre. Les longueurs de programmes et leurs temps d'exécution dépendent du langage universel choisi. Une comparaison quantitative exige la même machine de référence.
Le calcul exact n'est pas une procédure générale. Déterminer K(x), puis certifier le programme admissible le plus rapide, rencontre les limites d'indécidabilité de la complexité algorithmique. Pour un objet concret, on établit surtout des bornes ou des résultats relatifs à un modèle fixé.
Compliqué ne signifie pas profond. Une suite aléatoire peut être difficile à compresser, mais un programme qui la contient littéralement l'imprime vite. À l'inverse, une suite périodique peut avoir une description courte et rapide : ces deux extrêmes peuvent être peu profonds.
Pour aller plus loin
La complexité de Kolmogorov approfondit la longueur minimale K(x), qui fixe la frontière des programmes admis dans la profondeur logique.
La machine de Turing fournit un modèle de calcul pour préciser ce que signifient programme, exécution et arrêt.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres