La complexité des systèmes, des physiques aux biologiques, est généralement évaluée par des mesures entropiques : entropie excédentaire, complexité statistique, profondeur thermodynamique. Ces mesures capturent bien les corrélations et la mémoire, mais ne distinguent pas l'information résultant d'un long calcul de celle simplement stockée. Autour de ce travail, des recherches voisines cherchent également des mesures de complexité à l'interface de la physique statistique et du calcul : analyse de la complexité de l'intrication, extraction de lois à partir du bruit, mesure du chaos sans connaissance des règles. Cependant, la plupart se concentrent sur les aspects entropiques ou informationnels, alors que ce travail met l'accent sur l'histoire computationnelle de l'état : combien de pas parallèles sont réellement nécessaires pour le construire.
La profondeur est définie comme le temps d'exécution de l'algorithme parallèle le plus rapide qui échantillonne les états du système avec la probabilité correcte. On utilise le modèle de machine parallèle à accès aléatoire (PRAM), où de nombreux processeurs effectuent des opérations synchrones sur une mémoire partagée. L'idée clé est de minimiser le temps parallèle, et non le volume de calcul ou le hasard. Pour illustrer, on considère des processus stochastiques simples : tirage à pile ou face sans mémoire, tirage à pile ou face avec mémoire, et processus de Santa Fe avec une distribution en loi de puissance à décroissance lente. Pour chacun, on construit un algorithme d'échantillonnage parallèle explicite et on évalue son temps d'exécution ; par exemple, pour le processus de Santa Fe, on parvient à un temps logarithmique grâce à une comparaison parallèle de toutes les paires d'indices.
Pour le tirage à pile ou face sans mémoire, la profondeur est constante, O(1), car tous les bits sont indépendants et générés simultanément. Pour la pièce avec mémoire, la profondeur est logarithmique, O(log T), car le produit de facteurs indépendants peut être calculé par la méthode « diviser pour régner ». Le processus de Santa Fe a une entropie excédentaire qui croît comme une loi de puissance T^β, mais sa profondeur est également logarithmique : les longues corrélations ne nécessitent pas un long calcul si elles peuvent être parallélisées. En revanche, l'agrégation limitée par diffusion (DLA) avec N particules semble nécessiter un nombre linéaire de pas parallèles, O(N), car sa croissance est intrinsèquement séquentielle : chaque particule doit attendre la précédente. Cela est confirmé par la P-complétude du problème de génération de DLA, ce qui indique l'absence d'algorithme parallèle efficace.
Ce travail se distingue des recherches voisines en déplaçant l'accent de l'entropie et de l'information vers la complexité computationnelle de la génération de l'état. Les travaux voisins mesurent la complexité par les corrélations, l'intrication ou la précision de mesure, alors qu'ici la complexité est liée au temps parallèle minimal nécessaire pour reproduire un état typique. Cela permet de distinguer les systèmes qui stockent simplement l'information de ceux qui la traitent activement. La profondeur est maximale : si dans un grand système il existe une petite sous-partie très complexe, la profondeur du système entier est déterminée par elle, et non par une moyenne sur le volume. Cette propriété rend la profondeur sensible aux objets rares et complexes, comme la biosphère terrestre face au Soleil.
Le principal problème est que la profondeur n'est pas calculable exactement ; on ne peut que la borner supérieurement en exhibant des algorithmes de plus en plus efficaces. À mesure que la compréhension du système s'approfondit, l'estimation de la profondeur peut diminuer, comme ce fut le cas pour le modèle d'Ising après la découverte de l'algorithme de Swendsen-Wang. Le développement futur nécessitera une théorie de la complexité de l'échantillonnage qui permette de prouver des bornes inférieures de profondeur, et pas seulement des bornes supérieures. Il est également important de relier la profondeur aux phénomènes émergents : lorsque de nouvelles structures à grande échelle apparaissent dans un système, la compréhension de leur dynamique peut réduire radicalement le temps de calcul nécessaire.
La mesure de profondeur peut être appliquée pour classer les systèmes complexes en physique, biologie, économie et d'autres domaines où les états sont décrits par des distributions de probabilité. Elle est utile pour comparer des modèles et identifier des systèmes dotés de calculs intégrés, comme les automates cellulaires ou les modèles basés sur des agents.
Il est nécessaire de développer des méthodes pour prouver des bornes inférieures de profondeur pour des systèmes spécifiques, afin de transformer les bornes supérieures en valeurs exactes. Il convient également d'étudier comment la profondeur est liée aux transitions de phase et aux phénomènes critiques, où la complexité est maximale.
Pour la physique statistique, le problème clé non résolu est le lien entre la complexité computationnelle et les propriétés physiques des systèmes, en particulier près des points critiques. La profondeur offre un langage formel pour discuter pourquoi certains systèmes nécessitent une simulation longue, tandis que d'autres peuvent être échantillonnés rapidement, et comment cela se rapporte au comportement émergent.
Cette section s'adresse à l'auteur du travail et à ses collègues. Les travaux voisins ont été trouvés par une recherche sémantique dans notre archive, et non par correspondance de mots. Nous n'évaluons pas : nous montrons le champ autour.
Ce que fait ce travail
L'article introduit une mesure appelée « profondeur parallèle », qui correspond au nombre minimal d'étapes parallèles sur une machine PRAM nécessaire pour générer un état typique du système. Pour des processus stochastiques simples (lancer de pièce sans mémoire, avec mémoire, processus de Santa Fe), des estimations analytiques de la profondeur sont obtenues : O(1), O(log T), O(log T) respectivement. Pour l'agrégation limitée par diffusion (DLA), il est montré que la profondeur semble être linéaire, O(N), ce qui est lié à la P-complétude du problème de génération.
Où est sa force
La profondeur capture l'histoire computationnelle d'un état, et pas seulement ses corrélations statistiques ; grâce à sa propriété de maximalité, elle est sensible aux sous-systèmes rares et complexes, comme la biosphère. Cela la distingue des mesures entropiques et ouvre la voie à la mesure de la complexité des systèmes capables de calcul.
Vers où avancer
À essayer
Pourquoi cela peut compter
Si la profondeur reflète réellement la capacité d'un système à effectuer des calculs, elle pourrait devenir un outil pour rechercher la vie ou l'intelligence dans l'Univers, en mettant en évidence les objets à haute complexité computationnelle parmi les données astrophysiques.
Travaux voisins dans notre archive
L'archive est vide autour de ce travail : l'analyse la plus proche n'est qu'à 0.53, contre 0,64 d'ordinaire. Il semble qu'on ait peu foré à côté.
Si un chercheur extraterrestre mesurait la complexité du système solaire par l'entropie, il se concentrerait sur le Soleil, qui contient presque toute la masse et l'entropie. Mais une mesure de profondeur pointerait vers la surface d'une petite planète, la Terre : la biosphère, dont la complexité provient d'une longue histoire évolutive, et non du volume.