The complexity of systems, from physical to biological, is usually assessed via entropy-based measures: excess entropy, statistical complexity, thermodynamic depth. These measures capture correlations and memory well, but they do not distinguish information that arises from a long computation from information that is merely stored. Surrounding this work are studies that also seek complexity measures at the intersection of statistical physics and computation: analysis of entanglement complexity, extracting laws from noise, measuring chaos without knowing the rules. However, most of them focus on entropic or informational aspects, whereas this work emphasizes the computational history of a state: how many parallel steps are actually needed to construct it.
Depth is defined as the running time of the fastest parallel algorithm that samples states of the system with the correct probability. The model used is a parallel random-access machine (PRAM), where many processors synchronously perform operations on shared memory. The key idea is to minimize parallel time, not the amount of computation or randomness. To illustrate, simple stochastic processes are considered: a memoryless coin toss, a coin toss with memory, and the Santa Fe process with a slowly decaying power-law distribution. For each, an explicit parallel sampling algorithm is constructed and its running time is estimated; for example, for the Santa Fe process, logarithmic time can be achieved by parallel comparison of all pairs of indices.
For a memoryless coin toss, depth is constant, O(1), since all bits are independent and generated simultaneously. For a coin with memory, depth is logarithmic, O(log T), because the product of independent factors can be computed by divide and conquer. The Santa Fe process has excess entropy growing as a power law T^β, but its depth is also logarithmic: long correlations do not require long computation if they can be parallelized. In contrast, diffusion-limited aggregation (DLA) with N particles appears to require a linear number of parallel steps, O(N), because its growth is inherently sequential: each particle must wait for the previous one. This is supported by the P-completeness of the DLA generation problem, indicating the absence of an efficient parallel algorithm.
This work differs from neighboring studies by shifting the emphasis from entropy and information to the computational complexity of generating a state. Neighboring works measure complexity through correlations, entanglement, or measurement precision, whereas here complexity is linked to the minimum parallel time needed to reproduce a typical state. This allows distinguishing systems that merely store information from those that actively process it. Depth is maximal: if a large system contains one small but highly complex subsystem, the depth of the whole system is determined by that subsystem, not by averaging over volume. This property makes depth sensitive to rare complex objects, such as Earth's biosphere against the backdrop of the Sun.
The main problem is that depth is not exactly computable; it can only be bounded from above by demonstrating increasingly efficient algorithms. As understanding of a system deepens, the depth estimate may decrease, as happened with the Ising model after the discovery of the Swendsen–Wang algorithm. Further development will require a theory of sampling complexity that would allow proving lower bounds on depth, not just upper bounds. It is also important to connect depth with emergent phenomena: when new large-scale structures arise in a system, understanding their dynamics could radically reduce the required computational time.
The depth measure can be applied to classify complex systems in physics, biology, economics, and other fields where states are described by probability distributions. It is useful for comparing models and identifying systems with built-in computation, such as cellular automata or agent-based models.
It is necessary to develop methods for proving lower bounds on depth for specific systems, to turn upper bounds into exact values. It is also worth investigating how depth relates to phase transitions and critical phenomena, where complexity is maximal.
For statistical physics, the key unsolved problem is the connection between computational complexity and physical properties of systems, especially near critical points. Depth offers a formal language for discussing why some systems require long simulations while others can be sampled quickly, and how this relates to emergent behavior.
This section is addressed to the author of the paper and their colleagues. Neighbouring works were found by meaning-based search across our archive, not by word overlap. We do not review: we show the field around the work.
What the work does
The paper introduces a measure called "parallel depth": the minimum number of parallel steps on a PRAM required to generate a typical state of a system. For simple stochastic processes (memoryless coin tossing, coin tossing with memory, and the Santa Fe process), analytical estimates of depth are derived: O(1), O(log T), and O(log T), respectively. For diffusion-limited aggregation (DLA), the depth appears to scale linearly as O(N), which is linked to the P-completeness of the generation problem.
Where its strength is
Depth captures the computational history of a state, not just its statistical correlations, and thanks to its maximality property, it is sensitive to rare, complex subsystems such as the biosphere. This sets it apart from entropy-based measures and opens a path toward measuring the complexity of systems capable of computation.
Where it could go next
Worth trying
Why this may matter
If depth truly reflects a system's capacity for computation, it could become a tool for searching for life or intelligence in the universe, singling out objects with high computational complexity among astrophysical data.
Nearby works in our archive
The archive is sparse around this work: the closest review is only 0.53, against a usual 0.64. It looks like few have drilled nearby.
If an alien researcher measured the complexity of the Solar System by entropy, they would focus on the Sun, where almost all the mass and entropy are concentrated. But a depth measurement would point to the surface of a small planet, Earth: the biosphere, whose complexity arises from a long evolutionary history, not from volume.