Une équipe d'assembleurs de puzzle avec des pièces aléatoires : combien de mouvements simultanés faut-il pour reconstituer l'image ? Si les pièces sont indépendantes, toutes se placent d'un coup. Si chacune dépend de la précédente, il faut procéder une par une. Il en va de même pour les systèmes : certains états se rassemblent instantanément, d'autres exigent un long travail séquentiel.
La mesure proposée par l'auteur s'appelle profondeur parallèle. C'est le nombre minimal d'étapes simultanées sur un ordinateur idéalisé à multiples processeurs, nécessaire pour reproduire l'état typique d'un système. La profondeur ne demande pas combien de calculs ou de hasard au total, seulement combien de temps parallèle. Pour un lancer de pièce sans mémoire, la profondeur est constante : tous les bits sont indépendants et générés en même temps. Pour une pièce avec mémoire, la profondeur est logarithmique : le produit de facteurs indépendants peut être calculé par la méthode « diviser pour régner ».
Autre chose est l'agrégation limitée par diffusion (croissance d'un amas de particules par marche aléatoire). Ici, chaque particule doit attendre la précédente, et la profondeur croît linéairement avec le nombre de particules. La tâche de générer un tel amas est P-complète : il n'existe pas d'algorithme parallèle rapide. La profondeur est maximale : si dans un grand système il y a 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.
Auparavant, on ne savait pas distinguer les systèmes qui stockent simplement des corrélations complexes de ceux qui effectuent réellement de longs calculs. Maintenant c'est clair : la profondeur est faible pour les processus à mémoire, mais élevée pour les processus séquentiels comme l'agrégation limitée par diffusion. La mesure peut être appliquée pour classer les systèmes complexes en physique, biologie, économie, partout où les états sont décrits par des distributions de probabilité. Le principal problème est que la profondeur ne peut pas être calculée exactement ; on ne peut que la borner supérieurement en démontrant des algorithmes de plus en plus efficaces. Mais dès maintenant, elle aide à voir où se cachent de véritables calculs dans un système.
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.