En théorie algorithmique de l'information, la sophistication est une mesure de la complexité dérivée à partir de la complexité de Kolmogorov.
La sophistication cherche à représenter la complexité d'un objet en séparant la part de complexité de l'objet tant que représentant « générique » d'une catégorie d'objets plus large, par rapport à la complexité intrinsèque de l'ensemble représentatif. Le but étant de capturer uniquement la part de complexité non-aléatoire de l'objet.
Ainsi, si l'on considère comme objets les chaîne binaires de longueur N, on étudie la catégorie des chaînes dont les bits sont doublés, telles que 111100111100001100... . La sophistication d'une telle chaîne appartenant à cette catégorie est la complexité de la description qui représente le doublement des bits, étant donnés les N/2 bits nécessaires à décrire la chaîne.
Définition Soit K la complexité de Kolmogorov et c une constante, on définit la sophistication de x par:
La constante c est appelée significativité. On restreint l'ensemble S aux sous-ensembles finis de l'espaces des objets considérés
Voir aussi
Profondeur logique
Références
Pour en savoir plus
Liens externes
La première loi de la complexodynamique
Catégorie:Théorie algorithmique de l'information