Profondeur de Bennett
La profondeur de Bennett (ou profondeur logique de Bennett) est une mesure de la complexité en informatique, créée par le physicien et logicien américain Charles H. Bennett.
Elle vient en complément de la complexité de Kolmogorov : si celle-ci mesure la longueur du plus petit programme écrit pour créer une suite binaire, la profondeur de Bennett mesure, en nombre de pas, le temps de calcul de ce programme.
Comme son nom veut l'indiquer, cette mesure ajoute une seconde dimension à la théorie de la complexité ou, plus précisément, à la théorie algorithmique de l'information. Par exemple, une image entièrement blanche et une image entièrement aléatoire (en pixels noirs ou blancs) auront des valeurs de complexité de Kolmogorov très différentes (faible pour l'image blanche, forte pour l'image totalement aléatoire), mais auront toutes deux de faibles valeurs de profondeur de Bennett.
Références
modifier- Jean-Paul Delahaye, Conférence au colloque Émergences, (texte intégral, format .doc)
- Vidéo d'une conférence de Jean-Paul Delahaye en 2009, sur le site de Mi2s.
