A Statistical Measure of Complexity

This paper is a survey dedicated to the analogy between the notions of {\it complexity} in theoretical computer science and {\it energy} in physics. This analogy is not metaphorical: I describe three precise mathematical contexts, suggested recently, in which mathematics related to (un)computability is inspired by and to a degree reproduces formalisms of statistical physics and quantum field theory.

We will review some of the theoretical progresses that have been in the study of complex systems in physics and of their applications to biology.

We propose a new interpretation of objective deterministic chances in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set--up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the `distance' (in terms of physical resources) of a physical state from another, and (3) the size of the set of time--complexity functions t...

The use of algorithmic information theory (Kolmogorov complexity theory) to explain the relation between mathematical probability theory and `real world' is discussed.

We study the build up of complexity on the example of 1 kg matter in different forms. We start on the simplest example of ideal gases, and then continue with more complex chemical, biological, life and social and technical structures. We assess the complexity of these systems quantitatively, based on their entropy. We present a method to attribute the same entropy to known physical systems and to complex organic molecules up to a DNA. The important steps in this program and t...

Prediction of events is the challenge in many different disciplines, from meteorology to finance; the more this task is difficult, the more a system is {\it complex}. Nevertheless, even according to this restricted definition, a general consensus on what should be the correct indicator for complexity is still not reached. In particular, this characterization is still lacking for systems whose time evolution is influenced by factors which are not under control and appear as ra...

There is no single definition of complexity (Edmonds 1999; Gershenson 2008; Mitchell 2009; De Domenico, et al., 2019), as it acquires different meanings in different contexts. A general notion is the amount of information required to describe a phenomenon (Prokopenko, et al. 2008) , but it can also be understood as the length of the shortest program required to compute that description, as the time required to compute that description, as the minimal model to statistically de...

In recent studies, new measures of complexity for nonlinear systems have been proposed based on probabilistic grounds, as the LMC measure (Phys. Lett. A {\bf 209} (1995) 321) or the SDL measure (Phys. Rev. E {\bf 59} (1999) 2). All these measures share an intuitive consideration: complexity seems to emerge in nature close to instability points, as for example the phase transition points characteristic of critical phenomena. Here we discuss these measures and their reliabili...

Quantifying the complexity of systems consisting of many interacting parts has been an important challenge in the field of complex systems in both abstract and applied contexts. One approach, the complexity profile, is a measure of the information to describe a system as a function of the scale at which it is observed. We present a new formulation of the complexity profile, which expands its possible application to high-dimensional real-world and mathematically defined system...

The best way to model, understand, and quantify the information contained in complex systems is an open question in physics, mathematics, and computer science. The uncertain relationship between entropy and complexity further complicates this question. With ideas drawn from the object-relations theory of psychology, this paper develops an object-relations model of complex systems which generalizes to systems of all types, including mathematical operations, machines, biologica...