Ways to measure complexity

From: jimruttshow8596

Measuring complexity is a long-standing challenge, with many different approaches proposed across various fields [01:25:27]. Seth Lloyd began working on this problem around 1986 or 1987, inspired by a challenge from his supervisor Hein Pagels to develop a mathematical measure of complexity [01:38:00]. However, complexity is inherently difficult to characterize and measure [02:06:00].

At the Santa Fe Institute, where complexity theory is a core focus, there were as many as 20 different ideas on how to measure it from different researchers [02:24:00]. Lloyd himself once gave a talk titled “31 Measures of Complexity” [02:40:00]. The fundamental issue is that complexity is a broad class of phenomena that applies to qualitatively different systems, meaning each field often develops its own suitable measures [04:50:00]. Even seemingly simple entities, like an electron, require complex theory to understand, and interactions between multiple simple entities, such as the three-body problem in gravity, quickly become complex [03:02:00].

The metabolism of a bacterium serves as a good example of a truly complex system, involving thousands of chemical reactions and feedback loops, yet quantifying its complexity with a single number remains difficult [03:40:00].

Measures of Complexity

Algorithmic Complexity (Kolmogorov Complexity)

Algorithmic complexity, also known as Kolmogorov complexity, measures the shortest possible computer program required to generate a given sequence or object [08:36:00].

• Ordered Systems: Highly ordered or simple sequences, like a billion ones (“1111…”), have very low algorithmic complexity because a short program can generate them (e.g., “print one a billion times”) [07:30:00].
• Disordered Systems: Completely disordered or random sequences, like static on a TV screen or a coin flip sequence, have high algorithmic complexity because the shortest program to describe them is essentially the sequence itself, as there’s no way to compress it [08:58:00].
• Limitation: While it accurately captures the simplicity of ordered things, it assigns high complexity to random data, which is often not intuitively considered complex [09:25:00]. A system desired to be “complex” should require a lot of information to describe but should not be random [09:25:00].

Shannon Entropy

Shannon entropy is a measure of information that quantifies the amount of uncertainty or randomness in a system or message [10:10:00].

• Historical Connection: It shares the same mathematical formula developed by 19th-century physicists like James Clerk Maxwell, Ludwig Boltzmann, and Josiah Willard Gibbs to describe thermodynamic entropy, realizing that entropy is the information required to describe the positions of atoms and molecules [10:17:00].
• Compression: Shannon was interested in how efficiently messages could be compressed, taking into account statistical regularities [11:41:00]. For instance, a billion ones can be easily compressed to a short instruction [11:57:00].

Logical Depth

Introduced by Charles Bennett, logical depth measures complexity by the computational time required to produce an object from its shortest possible description [12:17:00].

• Distinction: Unlike algorithmic complexity, logical depth differentiates between simple ordered sequences (e.g., a billion ones, easy to produce) and purely random sequences (which are also easy to produce by simply listing them) [12:44:00], [15:10:00].
• Example: Pi: The first billion digits of Pi are considered logically deep [13:00:00]. While there are short programs to calculate Pi (e.g., the ancient Greek method of inscribing polygons), these computations take a long time to produce many digits [13:51:00], [15:38:00].
• Cellular Automata: Complex patterns generated by cellular automata, such as Wolfram’s Rule 110, are also logically deep because their generation requires executing all intermediate steps [16:05:00].

Thermodynamic Depth

Defined by Seth Lloyd and Hein Pagels for Lloyd’s PhD thesis, thermodynamic depth is a physical analogue of logical depth [18:48:00].

• Physical Resources: It measures the amount of physical resources, specifically free energy, that had to be consumed and dissipated to assemble a system from its initial state [19:06:00].
• Example: Bacterium Metabolism: The thermodynamic depth of bacterial metabolism is “humongous” because it took billions of years of evolution and immense energy consumption through natural selection to produce such complex organization [19:36:00].
• Connection to Computation: It can be mathematically and physically defined and connected to computational measures through the physics of computation [20:00:00].

Effective Complexity

Developed by Murray Gell-Mann and Seth Lloyd, effective complexity combines physical and computational notions of complexity [21:18:00].

• Distinction: It focuses on the “non-random” structured information necessary to describe a system, discarding the purely random or chaotic information (entropy) [22:57:00].
• Example: Air in a Room: The effective complexity of air in a room would describe macroscopic properties like percentages of gases, temperature, and pressure (tens to hundreds of thousands of bits), not the vast, random microscopic motions of individual molecules (tens of billions of billions of bits) [21:45:00].
• Example: Bacterium: For a bacterium, it would encompass the description of its metabolic organization and DNA required for its function (e.g., reproduction), abstracting away individual molecular wiggling [24:00:00].
• Subjectivity: Defining effective complexity requires defining the “purpose” or important features of the system, which can introduce a subjective element [26:05:00].
• Coarse-Graining: This measure utilizes the concept of coarse-graining, a technique for simplifying descriptions by ignoring fine-grained details and focusing only on relevant features at a particular scale [29:12:00].

Fractal Dimensions

Fractal dimensions are used to characterize the complexity of self-similar patterns found in nonlinear dynamical systems and chaos theory, such as snowflakes or the Lorenz attractor [30:37:00].

• Unpredictability vs. Predictability: While systems like weather are intrinsically unpredictable due to their chaotic nature (sensitive dependence on initial conditions), their dynamics are often confined to “strange attractors” with fractal structures. This confinement means that despite small-scale unpredictability, there can still be large-scale patterns and partial predictability [31:11:00], [34:55:00].

Lempel-Ziv Complexity (LZW)

Lempel-Ziv-Welch (LZW) complexity is a measure based on data compression algorithms [38:39:00].

• Adaptive Compression: Unlike Shannon entropy, which requires pre-calculating statistical regularities, LZW adaptively learns patterns in a message on the fly. It assigns shorter codes to increasingly frequent combinations of letters or words as it processes the data [38:59:00].
• Efficiency: LZW can encode and decode information efficiently, asymptotically achieving the Shannon bound for compression as message length increases [39:42:00].
• Application: LZW algorithms are widely used in file compression, such as ZIP and GIF formats [40:04:00]. A key property is that once a message is compressed, further compression does not reduce its size; rather, it typically makes it larger, as the compressed form is more random [40:51:00].

Statistical Complexity (Epsilon Machines)

Developed by Jim Crutchfield and Young, statistical complexity measures the size of the simplest computational machine (an automaton) that can reproduce a given message or text with the same statistical regularities [41:06:00].

• Computational Device: An automaton is a device with different states that produces outputs as it moves from state to state [42:15:00].
• Epsilon Machine: The “Epsilon machine” refers to the minimal automaton that can reproduce the statistical properties of a message up to a given accuracy (epsilon) [43:03:00].
• Relevance: This concept is relevant to modern large language models, which can be thought of as complex automata trained on vast text corpora to reproduce linguistic patterns [43:25:00].

Mutual Information

Mutual information quantifies the amount of information that different subsystems within a complex system possess in common [48:23:00].

• Shared Information: If two bits are always the same (e.g., 00 or 11), they share one bit of mutual information [48:55:00].
• Symptom of Complexity: Mutual information is often a symptom of complexity; it is difficult to imagine a complex system without a high degree of shared information and communication between its parts, like the components of a bacterium’s metabolism [49:32:00].
• Limitation: However, a high mutual information alone does not guarantee complexity. A system of a billion identical bits, for example, has high mutual information but is not considered complex [49:50:00]. It is a necessary but insufficient condition for complexity [50:44:00].

Integrated Information

Developed by Giulio Tononi, integrated information is a more intricate form of mutual information, often associated with theories of consciousness [51:00:00].

• Interdependence: It measures the extent to which a system’s parts are causally interdependent and contribute to the system’s overall state in a way that cannot be reduced to the sum of its parts [52:03:00].
• High in Complex Systems: Systems like brains or bacteria have high integrated information due to extensive communication and interconnected processes [51:51:00].
• Distinction from Complexity: Like mutual information, a high degree of integrated information does not necessarily mean a system is complex in an intuitive sense. For example, a simple error-correcting code can have high integrated information because every part of the system redundantly contains information about the message, allowing reconstruction even if many bits are corrupted [52:41:00].

Network Complexity

Network complexity refers to a class of ideas concerning the structure and behavior of complex networks [57:21:00].

• Examples: These include communication networks, neural connections in the brain, and power grids [57:29:00].
• Structure and Dynamics: Network complexity involves understanding the varied components (e.g., power plants of different sizes and types in a grid) and how their interconnections lead to emergent, often unforeseen, dynamic behaviors. These systems can exhibit chaotic regimes, especially when pushed to their operational limits [58:02:00].

Multiscale Entropy

Multiscale entropy assesses the amount of information present in a system at different levels of coarse-graining (or scales) [01:00:20].

• Scale-Dependent Information: A system is described by focusing on specific features at a particular scale, discarding information at finer scales. For example, gas in a room can be described by temperature and pressure, ignoring individual molecule movements [01:00:41].
• Information Across Scales: Complex systems, particularly living systems or networks, tend to possess a significant amount of information at each successive scale [01:01:10]. For instance, a human body is complex at the macroscopic level, the organ level, the cellular level, and even within cellular organelles like mitochondria [01:01:27].
• Symptom, Not Cause: Similar to mutual and integrated information, high multiscale entropy is a symptom of complexity, but not a sole determinant. Simple fractal systems, for example, exhibit multiscale information but may not be considered highly complex [01:02:50].

Conclusion

The discourse on complexity reveals that there is no single, universally applicable measure of complexity [01:03:14]. Instead, there are many different approaches, each with its own practical applications and limitations [01:03:20]. The choice of measure often depends on the specific domain and the purpose of the analysis, whether it’s quantifying descriptive difficulty, the effort required to create something, or the functional aspects of an engineered system [01:03:50].