COMPLEXITE ORGANISEE (ou profondeur logique, ou complexité de Bennett)

Source: http://www.peiresc.org/DINER/Lexique.pdf

 

Temps de calcul de l'algorithme le plus court décrivant l'objet ou temps de calcul du programme minimal engendrant l'objet. Un objet profond, c .a. d. ayant une grande profondeur logique est un objet dont l'origine la plus probable est un long calcul. C'est un objet qui contient des redondances profondément cachées en lui que seul un long travail combinatoire peut faire apparaître, lui enlevant ainsi tout caractère aléatoire. Un objet profond porte réellement en lui la trace d'une longue évolution. Mais comme pour la complexité aléatoire qui intervient dans sa définition, calculer avec certitude la profondeur logique d'un objet est une tâche impraticable. La relation entre complexité aléatoire et complexité organisée manifeste la complémentarité qui existe toujours entre la complexité descriptive (longueur du programme) et la complexité computationnelle (temps de calcul). Un programme court est loin de garantir un temps de calcul rapide. En particulier lorsqu'un programme comporte des boucles, sa formulation est relativement courte mais le temps de calcul peut s'avérer très long. L'information contenue dans un algorithme s'y trouve à l'état potentiel ou virtuel et nécessite un temps plus ou moins long pour en être extraite ou actualisée.