Towards a Universal Measure of Complexity

Abstract

Recently, it has been argued that entropy can be a direct measure of complexity, where the smaller value of entropy indicates lower system complexity, while its larger value indicates higher system complexity. We dispute this view and propose a universal measure of complexity that is based on Gell-Mann’s view of complexity. Our universal measure of complexity is based on a non-linear transformation of time-dependent entropy, where the system state with the highest complexity is the most distant from all the states of the system of lesser or no complexity. We have shown that the most complex is the optimally mixed state consisting of pure states, i.e., of the most regular and most disordered which the space of states of a given system allows. A parsimonious paradigmatic example of the simplest system with a small and a large number of degrees of freedom is shown to support this methodology. Several important features of this universal measure are pointed out, especially its flexibility (i.e., its openness to extensions), suitability to the analysis of system critical behaviour, and suitability to study the dynamic complexity.

1. Introduction

Analysis of the concept of complexity is a non-trivial task due to its diversity, arbitrariness, uncertainty, and contextual nature [1,2,3,4,5,6,7,8,9,10]. There are many different levels/scales, faces, and types of complexity, researched with very different technologies/techniques and tools [11,12,13] (and refs. therein). In the context of dynamical systems, Grassberger suggested [14] that a slow convergence of the entropy to its extensive asymptotic limit is a signature of complexity. This idea was materialized [15,16] further by information and statistical mechanics techniques. It generalizes many previous approaches to complexity, unifying physical ideas with ideas from learning and coding theory [17]. There also exists a connection of this approach to algorithmic or Kolmogorov complexity. The hidden pattern can be the essence of complexity [18,19,20,21]. Techniques adapted from the theories of information and computation have led physical science (in particular, the region extended between classical determinism and deterministic chaos) to discover hidden patterns and quantify their dynamic structural complexity [22]. The above approaches are not universal—they only capture small fragments of the concept of complexity.

We must remember that complexity also depends on the conditions imposed (e.g., boundary or initial conditions), as well as the restrictions adopted. This creates a challenge for every complexity study. It concerns the complexity that can appear in the movement of a single entity and collection of entities braided together. These entities can be irreducible or straightforward, simple systems, but they can also be complex systems.

When we talk about complexity, we mean irreducible complexity, which can no longer be divided into smaller sub-complexities. We refer to this as a primary complexity. Considering the primary complexity here, we mean one that can be expressed at least in an algorithmic way—it is an effective complexity if it also contains a logical depth [23,24,25,26,27]. We should take into account that our models (analytical and numerical) and theories describing reality are not fully deterministic. The evolution of a complex system is potentially multi-branched and the selection of an alternative trajectory (or branch selection) is based on decisions taken randomly.

One of the essential questions concerning a complex system is the problem of its stability/robustness and the question of the stationarity of its evolution [28]. Moreover, the relationship between complexity and disorder on the one hand, and complexity and pattern on the other is an important question—especially in the context of irreversible processes, where non-linear processes, running away from the equilibrium, play a central role. Financial markets can be a spectacular example of these processes [29,30,31,32,33,34,35,36,37,38,39].

The central question of whether entropy is a direct measure of complexity is one we answer in the negative. In our opinion, based on the Gell–Mann concept of complexity, the measure of complexity is appropriately, non-linearly transformed entropy. This work is devoted to finding this transformation and examining the resulting consequences.

2. Definition of a Universal Measure of Complexity and Its Properties

In this Section, we translate the Gell–Mann general qualitative concept of complexity into the language of mathematics, and we present the consequences of this.

2.1. The Gell–Mann Concept of Complexity

The problem of defining a universal measure of complexity is urgent. For this work, the Gell–Mann concept [23,40] of complexity is the inspirational starting point. We apply this concept to irreversible processes, by assuming that both fully ordered and fully disordered systems cannot be the complex. The fully ordered system essentially has no complexity because of maximal possible symmetry of the system, but the fully disordered system contains no information as it entirely dissipates. Hence, the maximum of complexity should be sought somewhere in between these pure extreme states. This point of view allows for the introduction of a formal quantitative phenomenological complexity measure based on entropy as a parameter of order [29,41]. This measure reflects the dynamics of the system through the dependence of entropy on time. The vast majority of works analyzing the general aspects of complexity, including its basis, are based on information theory and computational analysis. Such an approach requires supplementing with a provision allowing a return from a bit representation to physical representation—only this will allow physical interpretations, including understanding of the causes of complexity.

We define the phenomenological partial measure of complexity as a non-linear function of entropy S of the order of $(m,n)$,

$$\begin{array}{ccc}CX(S;m,n)\hfill & \stackrel{\mathrm{def}.}{=}\hfill & {(S^{max}-S)}^m{(S-S^{min})}^n\hfill \\ \hfill & \hfill =& \hfill CX(S;m-1,n-1)\left[{\left(\frac{Z}{2}\right)}^2-{(S-S^{arit})}^2\right],m,n\ge 1,\end{array}$$

(1)

where $S^{min}$ and $S^{max}$ are minimal and maximal values of entropy S, respectively, $S^{arit}=\frac{S^{min}+S^{max}}{2}$, and the entropic span $Z\stackrel{\mathrm{def}.}{=}{S}^{max}-S^{min}$, whereas m and n are natural numbers (an extension to real positive numbers is possible but this is not the subject of this work). They define the order $(m,n)$ of the partial measure of complexity $CX$. Let us add that this formula is also applicable at a mesoscopic scale. In other words, complexity appears in all systems for which we can build entropy. Notably, $S^{max}$ does not have to concern the state of thermodynamic equilibrium of the system. It may refer to the state for which entropy reaches its maximum value in the observed time interval. However, in this work, we are only limited to systems having a state of thermodynamic equilibrium. Below, we discuss the Equation (1), indicating that it satisfies all properties of the measure of complexity. Of course, when $m=0$ and $n=1$ then $CX$ simply becomes $S-S^{min}$, i.e., the entropy of the system (the constant is not important here). However, when $m=1,n=0$, we obtain the information contained in the system (constant does not play a role here). Equation (1) gives us a lot more—showing this is the purpose of this work (helpful features of CX are shown in Appendix A).

The partial measure of complexity given by Equation (1) is determined with the accuracy of the additive constant of S, i.e., this constant does not contribute to the measure of the complexity of the system.

Using Equation (1), we can also enter the partial measure of specific complexity, as follows,

$$\begin{array}{c}\hfill cx(s;m,n)\stackrel{\mathrm{def}.}{=}\frac{1}{N^{m+n}}CX(Ns;m,n),\end{array}$$

(2)

where N is the number of entities that make up the system and specific entropy $s=S/N$. As one can see, the partial measure of specific complexity $cx$ is independent of N for an extensive system. Specific entropy and specific complexity are particularly convenient when comparing different extensive systems and when we do not examine the complexity dependence on N.

However, the extraction of an additional multiplicative constant (e.g., particle number) to have s independent of N often presents a technical difficulty, or may even be impossible, especially for non-extensive systems. Then it is more convenient to use the entropy of the system instead of the specific entropy. It is also important to realize that determining extreme entropy values (or extreme specific entropy values) of actual systems can be complicated and it requires additional dedicated tools/technologies, algorithms, and models.

The partial measures of complexity are enslaved by entropy in every order $(m,n)$ of complexity. However, the kind of entropy we use in Equation (1) depends on the specific situation of the system and what we want to know about the system, because our definition of complexity does not specify this. From our point of view, relative entropies formulated in the spirit of Kullback–Leibler seem to be the most appropriate (this is referred to in Appendix B). Using the Kullback–Leibler type of entropy, one can express both ordinary entropies and conditional entropies, in particular one can describe the entropy rate increasingly used in the context of complexity analysis.

The entropy here can be both additive (the Boltzmann–Gibbs thermodynamic one [42], Shanon information [17], Rényi [43]), and non-additive entropy (Tsallis [44]). The measure $CX\left(S\right)$ is a concave (or convex up) function of entropy S, which disappears on the edges at points $S=S^{min}$ and $S=S^{max}$.

It has a maximum

$$\begin{array}{c}\hfill C{X}^{max}=CX(S=S_{CX}^{max};m,n)=m^m{n}^n{\left(\frac{Z}{m+n}\right)}^{m+n}\end{array}$$

(3)

at point

$$\begin{array}{c}\hfill S=S_{CX}^{max}=\overline{S}=\frac{m{S}^{min}+n{S}^{max}}{m+n}=\frac{\frac{1}{m}{S}^{max}+\frac{1}{n}{S}^{min}}{\frac{1}{m}+\frac{1}{n}}\end{array}$$

(4)

as at this point $\frac{dCX\left(S\right)}{dS}{\mid }_{S=\overline{S}}=0$ and $\frac{d^{2}CX\left(S\right)}{d{S}^2}{\mid }_{S=\overline{S}}<0$. The quantity $S_{CX}^{max}$ is a characteristic also because it is a weighted average. The quantity $C{X}^{max}$ is well suited to global universal measurements of complexity, because (at a given order $(m,n)$), it only depends on the entropy span Z. The quantity $c{x}^{max}\stackrel{\mathrm{def}.}{=}C{X}^{max}/N^{m+n}$ might also be a good candidate for measuring the logic depth of complexity.

2.2. The Most Complex Structure

The question now arises about the structure of the system corresponding to entropy $S_{CX}^{max}$ given by Equation (4). The answer is given by the following constitutive equation,

$$\begin{array}{c}\hfill S\left(Y=Y^{C{X}^{max}}\right)=S_{CX}^{max},\end{array}$$

(5)

where Y is the set of variables and parameters (e.g., thermodynamic), on which the state of the system depends. However, $Y=Y^{C{X}^{max}}$ is a set of such values of these variables and parameters that are the solution of Equation (5). This solution gives the entropy value $S=S_{CX}^{max}$ that maximizes the partial measure of complexity, that is $CX=C{X}^{max}$. Hence, with the value of $Y^{C{X}^{max}}$, we can finally answer the key question: what structure/pattern is behind $C{X}^{max}$ or what the structure of maximum complexity looks like.

There are a few comments to be made regarding the constitutive Equation (5) itself. It is a (non-linear) transcendental equation in the untangled form relative to the Y. This equation should be numerically solved, because we do not expect it to have an analytical solution for maximally complex systems. An instructive example of a specific form of this equation and its solution for a specific physical problem is presented in Section 3. However, this will help us to understand how our machinery works.

Equation (4) legitimizes the measure of complexity we have introduced. Namely, its maximum value falls on the weighted average entropy value, which describes the optimal mixture of completely ordered and completely disordered phases. To the left of $\overline{S}$, we have a phase with dominance of order and to the right a phase with dominance of disorder. The transition between both phases at $\overline{S}$ is continuous. Thus, we can say that the partial measure of complexity that we have introduced also defines a certain type of phase diagram in S and $CX$ variables (phase diagram plain). Section 2.5 provides more detailed information.

2.3. Evolution of the Partial Measure of Complexity

Differentiating Equation (1) over time t, we obtain the following non-linear dynamics equation,

$$\begin{array}{c}\hfill \frac{dCX\left(S\right(t);m,n)}{dt}={\chi }_{CX}(S;m,n)\frac{dS\left(t\right)}{dt}=(m+n)\left[S_{CX}^{max}-S\left(t\right)\right]CX(S\left(t\right);m-1,n-1)\frac{dS\left(t\right)}{dt},\end{array}$$

(6)

where the entropic S-dependent (non-linear), susceptibility is defined by

$$\begin{array}{c}\hfill {\chi }_{CX}(S;m,n)\stackrel{\mathrm{def}.}{=}\frac{\partial CX(S;m,n)}{\partial S}=(m+n)\left[S_{CX}^{max}-S\left(t\right)\right]CX(S\left(t\right);m-1,n-1)\end{array}$$

(7)

and $\frac{dS\left(t\right)}{dt}$ can be expressed, for example, using the right-hand side of the master Markov equation (see Ref. [45] for details). However, we must realize that the dependence of entropy on time can, in general, be non-monotonic, because real systems are not isolated (cf. the schematic plot in Figure 2). One can see how the dynamics of complexity is controlled in a non-linear way by the evolution of the entropy of the system.

In concluding this Section, we state that Equations (1)–(6) together provide a technology for studying the multi-scale aspects of complexity, including the dynamic complexity. However, it is still a simplified approach, as we show in Section 4.

2.4. Significant Partial Measure of Complexity

We consider the partial measure of complexity to be significant when the entropy of the system is located between two inflection points of the $CX(S;m,n)$ curve, i.e., in the range $S_{ip}^{-}\le S\le S_{ip}^{+}$. This case occurs for $n,m\ge 2$. We then obtain

$$\begin{array}{c}\hfill S^{min}<S_{ip}^{\mp }=S^{min}+\frac{n(n-1)}{\sqrt{n(n+m-1)}}\frac{S^{max}-S^{min}}{\sqrt{n(n+m-1)}\pm \sqrt{m}}<S^{max},\end{array}$$

(8)

see Figure 1d for details.

There are two different cases where a single inflection point is present. Namely,

$$\begin{array}{cc}\hfill S^{min}<S_{ip}^{-}=\frac{2S^{max}+m(m-1)S^{min}}{2+m(m-1)}<\overline{S},& \mathrm{for}m\ge 2,n=1,\end{array}$$

(9)

and

$$\begin{array}{cc}\hfill \overline{S}<S_{ip}^{+}=\frac{2S^{min}+n(n-1)S^{max}}{2+n(n-1)}<S^{max},& \mathrm{for}m=1,n\ge 2.\end{array}$$

(10)

In Figure 1b, we present the case defined by Equation (9), while that defined by Equation (10) is shown in Figure 1c.

For $n=m=1$, the curve $CX(S;m,n)$ vs. S has no inflection points and it looks like a horseshoe (cf. Figure 1a).

Notably, we can equivalently write

$$\begin{array}{cc}\hfill S^{min}<S_{ip}^{\mp }=S^{max}-\frac{m(m-1)}{\sqrt{m(n+m-1)}}\frac{S^{max}-S^{min}}{\sqrt{m(n+m-1)}\mp \sqrt{n}}<S^{max},& \mathrm{for}n,m\ge 2.\end{array}$$

(11)

Let us consider the span $Z_{ip}=S_{ip}^{+}-S_{ip}^{-}$ of the two-phase area. From Equation (8), or equivalently from Equation (11), we obtain

$$\begin{array}{c}\hfill Z_{ip}=\frac{2\sqrt{nm}}{(n+m)\sqrt{n+m-1}}Z.\end{array}$$

(12)

As one can see, the span $Z_{ip}$ depends linearly on the span Z and in a non-trivial way on the exponents n and m. Thus, with the Z set, only $Z_{ip}$’s non-trivial dependence on the order $(m,n)$ of measure of complexity $CX$ occurs, which is different from $C{X}^{max}$ dependence. In other words, $Z_{ip}$ is less sensitive to complexity than $C{X}^{max}$.

The significant partial measure of complexity ranges between the two inflection points only for the case $n,m\ge 2$ (cf. Figure 1d). Indeed, a mixture of phases is observed in this area. For areas where $S^{min}\le S<S_{ip}^{-}$ and $S_{ip}^{+}<S\le S^{max}$, we have (practically speaking) only single phases, ordered and disordered, respectively (see Section 2.5 for details). The case defined by Equation (8), and equivalently by Equation (11), is the most general, while taking into account the fullness of complexity behaviour as a function of entropy. Other cases impoverish the description of complexity. Therefore, we will continue to consider the situation, where $n,m\ge 2$.

The choice of any of the $CX(S;m,n)$ forms (i.e., exponents n and m) is a somewhat arbitrary function of the state of the system as it depends on the function of the state, that is on the entropy. In our opinion, the shape of the $CX(S;m,n)$ measure vs. S we present in Figure 1d is the most appropriate, because only then the significant complexity is ranging between non-vanishing inflection points $S_{ip}^{-}$ and $S_{ip}^{+}$.

In generic case we should, however, use the series of partial measures defined by Equation (1). Then, we define the order of the partial complexity using the pair of exponents $(n,m)$. The introduction of the order of the partial complexity is in line with our perception of the existence of multiple levels of (full) complexity.

We are able to discover the nature of the $CX$ measure, i.e., its dynamics and, in particular, its dynamical structures, when we analyze the entropy dynamics $S\left(t\right)$ (see Figure 2 for details).

The measurability of the partial measure of complexity is necessary for characterizing it quantitatively and to be able to compare different complexities. Following Gell–Mann [40], we must identify the scales at which we perform the analysis and thus determine coarse-graining to define the entropy. Its dependence on complexity cannot be ruled out.

However, the question of direct measurement of the partial measure of complexity in an experiment (real or numerical) remains a challenge.

2.5. Remarks on the Partial Entropic Susceptibility

An essential tool for studying phase transitions is the system susceptibility—in our case, the partial entropic susceptibility of the partial measure of complexity. Here, it (additionally) plays the role of the partial order parameter.

The plot of susceptibility ${\chi }_{CX}(S;m,n)$ vs. S is presented in Figure 3. Four phases, already marked in Figure 1, are visible (also numbered 1 to 4).

Phase number 1 is almost entirely ordered—the disordered phase input is residual. At point $S_{ip}^{-}$, there is a phase transition to the mixed-phase marked with number 2, still with the predominance of the ordered phase. At the $S_{ip}^{-}$ inflection point, the entropic susceptibility reaches a local maximum. By further increasing the entropy of the system, it enters phase 3 as a result of phase transition at the very specific $S_{CX}^{max}$ transition point. At this point, the entropic susceptibility of the partial measure of complexity disappears. This mixed phase (number 3) is already characterized by the advantage of the disordered phase over the ordered one. Finally, the last transition, which occurs at $S_{ip}^{+}$, leads the system to the dominating phase of the disordered phase—the input of the ordered phase is residual here. At this transition point, the susceptibility reaches a local minimum. Intriguingly, entropic susceptibility can have both positive and negative value passing smoothly through zero at $S=S_{CX}^{max}$, where the system is exceptionally robust. The presence of phases with positive and negative entropic susceptibility is an exceptionally intriguing phenomenon. The phases discussed above, together with the above-mentioned inflection points, are also marked in Figure 1d. Let us add that the location of the phases mentioned above, i.e., the location of the inflection points, depends on the order $(m,n)$ of the partial measure of complexity. This is clearly seen in Figure 4 and Figure 5.

The values of local extremes of the entropic susceptibility of the partial measure of complexity are finite here and not divergent, as in the case of (equilibrium and non-equilibrium) phase transitions in the absence of an external field. We use this definition to describe the critical behaviour of a system that we demonstrate in Section 2.7, where it requires an explicit dependence on N.

2.6. Universal Full Measure of Complexity

The full universal measure of complexity X is a weighted sum of the partial measures of complexity $CX(S;m,n)$ for individual scales. That is,

$$\begin{array}{c}\hfill X(S;m_0,n_0)=\sum _{m\ge m_0,n\ge n_0}w(m,n)CX(S;m,n),m_0,n_0\ge 0,\end{array}$$

(13)

where $w(m,n)$ is a normalized weight, which must be given in an explicit form. This form is to some extent imposed by the power-law form of partial complexity. Namely, we can assume

$$\begin{array}{c}\hfill w(m,n)={\left(1-\frac{1}{M}\right)}^2\frac{1}{M^{m-m_0+n-n_0}},M>1,\end{array}$$

(14)

which seems to be particularly simple because

$$\begin{array}{c}\hfill \frac{w(m+1,n)}{w(m,n)}=\frac{w(m,n+1)}{w(m,n)}=\frac{1}{M},\end{array}$$

(15)

independently of m and n.

As one can see, Equation (13), supported by Equation (15), is the product of the sums of two geometric series,

$$\begin{array}{ccc}\hfill X(S;m_0,n_0)& \hfill =& \hfill {\left(S^{max}-S\right)}^{m_0}\left(1-\frac{1}{M}\right)\sum _{m\ge m_0}\frac{{\left(S^{max}-S\right)}^{m-m_0}}{M^{m-m_0}}\\ \hfill & \hfill \times & {\left(S^{max}-S\right)}^{n_0}\left(1-\frac{1}{M}\right)\sum _{n\ge n_0}\frac{{\left(S^{max}-S\right)}^{n-n_0}}{M^{n-n_0}}.\hfill \end{array}$$

(16)

If both series converge for any $S^{min}\le S\le S^{max}$, which is the case if and only if the condition $Z(=S^{max}-S^{min})<M$ is met, then we directly obtain

$$\begin{array}{c}\hfill X(S;m_0,n_0)={\left(1-\frac{1}{M}\right)}^2\frac{{(S^{max}-S)}^{m_0}}{1-\frac{S^{max}-S}{M}}\frac{{(S-S^{min})}^{n_0}}{1-\frac{S-S^{min}}{M}}.\end{array}$$

(17)

In other words, the M parameter can always be chosen, so that the sums of both series in Equation (21) diverge for all S values. Thus, $m_0,n_0\ge 1$ is the natural lower limit of $m_0,n_0$, satisfying the condition of $X(S;m_0,n_0)$ disappearing for $S=S^{min},S^{max}$. We still assume more strongly that $m_0,n_0\ge 2$, which has already been explained above.

For extensive systems, Equation (17) can be presented in a form that clearly shows the dependence of the X complexity on the number of entities N, simply replacing S entropy by $Ns$, where s is already N-independent specific entropy. Subsequently,

$$\begin{array}{c}\hfill X(Ns;m_0,n_0)={\left(1-\frac{1}{M}\right)}^2{N}^{m_0+n_0}\frac{{(s^{max}-s)}^{m_0}}{1-\frac{N}{M}(s^{max}-s)}\frac{{(s-s^{min})}^{n_0}}{1-\frac{N}{M}(s-s^{min})}.\end{array}$$

(18)

We emphasize that X does not scale with N, as opposed to partial measures of complexity.

In Figure 6 and Figure 7, we show the dependence of X on N (on the plane) and on N and s (in three dimensions), respectively. We obtained the singularities of full complexity, $N_j^{cr}\left(s\right),j=1,2$, as a result of the zeroing of denominators in the Equation (17) at nonzero numerators.

Note that, for $M\gg Z$, both measures of complexity have approximate values $X(S;m0,n0)\approx CX(S;m0,n0)$. Important differences between these two measures only appear for $Z/M$ close to 1, because only then does the denominator in Equation (17) play an important role. Of course, M is a free parameter, and possibly its specific value could be obtained from some additional (e.g., external) constraint.

In Figure 4, we compare the behaviour of the partial (black curve) and full (orange curve) measures of complexity, where we used the entropy instead of the specific entropy. Whether $CX$ lies below or above X depends both on M parameter (determining the weight at which individual measures of partial complexity enter the full measure of complexity), and on the $Z/M$ ratio.

We continue to determine the full entropic susceptibility of the full measure of complexity,

$$\begin{array}{ccc}\hfill {\chi }_X(S;m_0,n_0)& \hfill =& \hfill \frac{dX(S;m_0,n_0)}{dS}=(m_0+n_0)(S_{CX}^{max}-S)X(S;m_0-1,n_0-1)\\ \hfill & \hfill +& \frac{2}{M^2}X(S;m_0,n_0)\frac{S-S^{arit}}{\left(1-\frac{S^{max}-S}{M}\right)\left(1-\frac{S-S^{min}}{M}\right)},m_0,n_0\ge 1,\hfill \end{array}$$

(19)

where $S_{CX}^{max}$ is given here by Equation (4) but for $m=m_0$ and $n=n_0$. Notably, for the symmetric cases $m=n$ and/or $m_0=n_0$, we have $S_{CX}^{max}=S_X^{max}=S^{arit}$, which are independent of $m,m_0$.

Similarly to the partial entropic susceptibility of a partial measure of complexity, we obtain the full entropic susceptibility of a full measure of complexity,

$$\begin{array}{ccc}\hfill {\chi }_X(Ns;m_0,n_0)& \hfill =& \frac{dX(S;m_0,n_0)}{dS}=(m_0+n_0)N(s_{CX}^{max}-s)X(Ns;m_0-1,n_0-1)\hfill \\ \hfill & \hfill +& \hfill \frac{2}{M^2}X(Ns;m_0,n_0)N\frac{s-s^{arit}}{\left(1-\frac{N}{M}(s^{max}-s)\right)\left(1-\frac{N}{M}(s-s^{min})\right)},m_0,n_0\ge 1,\end{array}$$

(20)

where $s_{CX}^{max}=S_{CX}^{max}/N$, $s^{arit}=S^{arit}/N$, $s^{min}=S^{min}/N$, and $s^{max}=S^{max}/N$. The progression of susceptibility ${\chi }_X(S;m_0,n_0)$, depending on S, for selected parameter values is shown in Figure 5. This progression course is similar to the analogous one that is presented in Figure 3.

Thus, the evolution of X is governed by an equation that is analogous to Equation (6), except that ${\chi }_{CX}$ present in that equation should be replaced by ${\chi }_X$ given by Equation (19). Therefore, we have

$$\begin{array}{c}\hfill \frac{dX(S\left(t\right),m_0,n_0)}{dt}={\chi }_X(S\left(t\right);m_0,n_0)\frac{dS\left(t\right)}{dt}.\end{array}$$

(21)

The relationship between measures of complexity and time is implicit in our work—complexity indirectly depends on time through the dependence of entropy on time. It should be emphasized that the dependence of entropy on time is external in our approach—it can be taken into account based on additional modelling that is dedicated to specific real situations. We have already signalled this when discussing Equation (6).

2.7. Criticality in Extensive Systems

By using Equation (17), we show when the universal full measure of complexity diverges and, thus, the system enters a critical state. We assume that we are dealing with an extensive system, i.e., that Equation (17) can be represented as

$$\begin{array}{c}\hfill X(Ns;m_0,n_0)={\left(1-\frac{1}{M}\right)}^2{N}^{m_0+n_0}\frac{{(s^{max}-s)}^{m_0}}{1-\frac{N}{M}(s^{max}-s)}\times \frac{{(s-s^{min})}^{n_0}}{1-\frac{N}{M}(s-s^{min})},\frac{Nz}{M}<1,\end{array}$$

(22)

where entropy densities $s(=S/N),s^{min}(=S^{min}/N),s^{max}(=S^{max}/N)$ are (at most) slowly varying functions of the number N of elements making up the system and special entropy span $z=s^{max}-s^{min}$. As one can see, the measure X is divergent in two critical points $N_{cr}^{max}\left(s\right)=\frac{M}{s^{max}-s}$ and $N_{cr}^{min}\left(s\right)=\frac{M}{s^{min}-s}$, where $s^{min}<s<s^{max}$. Moreover, the susceptibilities given by Equations (19) and (20) diverge at the same points where measures of complexity given by Equations (17) and (18) diverge, which underlines the self-consistency of our approach.

Equation (22) can now be written in a form that explicitly includes both critical points (both physical and non-physical):

$$\begin{array}{c}\hfill X(Ns;m_0,n_0)={\left(1-\frac{1}{M}\right)}^2{N}^{m_0+n_0}\frac{{(s^{max}-s)}^{m_0}}{{\left(1-\frac{N}{N_{cr}^{max}\left(s\right)}\right)}^{{\beta }^{max}}}\times \frac{{(s-s^{min})}^{n_0}}{{\left(1-\frac{N}{N_{cr}^{min}\left(s\right)}\right)}^{{\beta }^{min}}},\end{array}$$

(23)

where critical exponents assume the mean-field values ${\beta }^{max}={\beta }^{min}=1$. In this case, we could speak of two-criticality were it not for the fact that one of these criticalities is unphysical.

Figure 6 shows dependence $X(Ns;m_0,n_0)$ vs. N at fixed $s=0.8$. The values of parameters are shown there, while the specific entropy s is chosen so that the condition $s-s^{min}<s^{max}-s$ is satisfied (this is equivalent to a condition $s<s^{arit}$). This means that s is closer to $s^{min}$ than $s^{max}$. The existence of these divergences is a signature of criticality. However, the situation for borderline cases $s=s^{min}$ or $s=s^{max}$ changes rapidly—it is a different consideration.

Critical numbers of entities in the system $N_{cr}^{max}\left(s\right)$ and $N_{cr}^{min}\left(s\right)$ are determined by the ratio of the M parameter characterizing the hierarchy/cascade of scales in the system and the distance between entropy density s and its extreme values $s^{min}$ and $s^{max}$. The construction of these critical numbers resembles the canonical critical temperature structure for the Ising model in the mean-field approximation, where ${\beta }_{c}Jz=1$ (here ${\beta }_c=1/k_B{T}_c$ and $k_B$ is the Boltzmann constant). In our case, the role of the inverse temperature ${\beta }_c$ is played by $N_{cr}^{max}$ and $N_{cr}^{min}$, the role of the coupling constant J is $1/M$, while the role of the mean coordination number z is played by $s^{max}-s$ and $s-s^{min}$, respectively.

The hierarchy is the source of criticality here. Criticality is an immanent feature of our full description of complexity. Nevertheless, in this work, we do not specify the sources of this hierarchy—it could be self-organized criticality or due to some other sources.

For the sake of completeness, note that the dependence on N of the partial measure of complexity is given by Equation (2). This means that for extensive systems this measure increases powerfully depending on N. Therefore, only the weighted infinite sum of these measures generates the existence of singularity.

Let us now consider in more detail the behaviour of $X(Ns;m_0,n_0)$ depending on N and s. A three-dimensional plot of Figure 7 will be helpful here. One can see how the mutual location of the singularities of $N_{cr}^{max}\left(s\right)$ and $N_{cr}^{min}\left(s\right)$ changes with the increase of s. From the situation of $s<s^{arit}$, in which $N_{cr}^{max}\left(s\right)>N_{cr}^{min}\left(s\right)$, through the situation when $s=s^{arit}$ in which $N_{cr}^{max}\left(s\right)=N_{cr}^{min}\left(s\right)$, up to the situation in which $N_{cr}^{max}\left(s\right)>N_{cr}^{min}\left(s\right)$ for $s>s^{arit}$.

It must be clearly stated that the area physically accessible is the one in front of the first singularity, which is further emphasized in Figure 7 by blue curves. Let us emphasize that the N range in which criticality occurs is sufficient to cover the corresponding values of N discussed in the literature to date, especially the Dunbar numbers [46,47,48,49] (e.g., $N=5,15,50$, and $N=150$). However, it should be noted that our view of complexity is complementary to that presented in the literature.

3. Finger Print of Complexity in Simplicity

Let us consider a perfect gas at a fixed temperature, which is initially closed in the left half of an isolated container. The partition is next removed, and the gas undergoes a spontaneous expansion. Here we are dealing (practically speaking) with an irreversible process, even for a small number of particles (at least the order of ${10}^2$).

Let us recall the definition of ’perfect gas’. It is a gas of particles that cannot ‘see’ each other, i.e., there are no interactions between them. Thus, from a physical point of view, it is a dilute gas at high temperature. We further assume that all of the particles have the same kinetic energy. A legitimate question is whether such a gas will expand after the partition is removed. We notice that the thermodynamic force is at work here, being roughly proportional to the difference in the number of particles in the right and left parts of the container. This force causes the expansion process. Thus, we are dealing with the simplest paradigmatic irreversible process [50]. The particles remain stuck in the final state and will not leave it (with accuracy subject to slight fluctuations in the number of particles in the right half of the container). Such a final state of the whole system is referred to as the equilibrium state. The simple coarse-grain description of the system allows us to introduce here the concept of configuration entropy.

Note that the macroscopic state of the system (generally, the non-equilibrium and non-stationary/relaxing one) can be described by the instantaneous number of particles in the left ($N_L\left(t\right)$) and right ($N_R\left(t\right)$) parts of the container, with $N=N_L\left(t\right)+N_R\left(t\right)$, where N is the fixed total number of particles in the container (isolated system). It allows for one to define the weight of the macroscopic state $\Gamma \left(N_L\left(t\right)\right)$, also called thermodynamic probability. This is the number of ways to arrange the $N_L\left(t\right)$ particles in the left part of the container and $N_R\left(t\right)=N-N_L\left(t\right)$ in the right. Hence,

$$\begin{array}{c}\hfill \Gamma \left(N_L\left(t\right)\right)=\frac{N!}{N_L\left(t\right)!(N-N_L\left(t\right))!}.\end{array}$$

(24)

Here we do not distinguish permutations of particles inside each part of the container separately. We only take into account permutations of particles located in different halves of the container. This is because our resolution here is too small to observe the location of particles inside each container separately. Such a coarse-graining creates an information barrier: more information can mask the complexity of the system. We will not be able to see the complexity, because we will not be able to construct entropy. This creates a paradoxical situation: the surplus of information makes the task difficult and does not facilitate obtaining the insight into the system. Here we have an analogy with chaotic dynamics, where chaos is only visible in the Poincaré surface cross-section of the phase space and not in the entire phase space.

The configuration entropy at a given time t we define, as follows,

$$\begin{array}{c}\hfill S\left(N_L\left(t\right)\right)=ln\Gamma \left(N_L\left(t\right)\right),\end{array}$$

(25)

where $\Gamma \left(N_L\left(t\right)\right)$ is given by Equation (24). The above expression can be used both for the equilibrium and non-equilibrium states.

It can be demonstrated using the Stirling formula that for large N, entropy S is reduced to the BGS form,

$$\begin{array}{c}\hfill ln\Gamma \left(N_L\left(t\right)\right)=-N\left[p_L\left(t\right)ln{p}_L\left(t\right)+p_R\left(t\right)ln{p}_R\left(t\right)\right]=Ns\left(t\right),\end{array}$$

(26)

where $p_J\left(t\right)\stackrel{\mathrm{def}.}{=}\frac{N_J\left(t\right)}{N},J=L,R$, and $s\left(t\right)$ is a specific entropy. The law of entropy increase Equation (A8) is also fulfilled here, as expected.

We now prepare the equation for determining $N_L^{C{X}^{max}}$, i.e., the number of particles in the left part of the container that maximizes the partial complexity measure $CX$. To this end, we assume, for instance, the symmetric partial measure of complexity of the order of $(m=2,n=2)$. Next, we substitute $N_L=N_L^{C{X}^{max}}$ into the both sides of Equation (25) and according to constitutive Equation (5), we equate Equation (25) to $S_{CX}^{max}$. Hence, we obtain a constitutive equation for the relaxing perfect gas,

$$\begin{array}{c}\hfill S(N_L\left(t\right)=N_L^{{CX}^{max}})=S_{CX}^{max},\end{array}$$

(27)

where $N_L^{{CX}^{max}}$ is our sought quantity.

Now, we need to independently determine $S_{CX}^{max}$. Recall that the number of $N_L$ particles that maximize entropy is the number of $N_L^{eq}$ particles in the statistical/thermodynamic equilibrium state of the system. This number is equal to half of all particles in the container, i.e., $N_L^{eq}=N/2$. It can still be assumed (without reducing the general considerations) that $S^{min}=0$. Therefore,

$$\begin{array}{c}\hfill S^{max}=S(N/2).\end{array}$$

(28)

However, from Equation (A5), we know that $S_{CX}^{max}=S^{max}/2$. By using it, we transform Equation (27) into the form,

$$\begin{array}{c}\hfill S\left(N_L^{{CX}^{max}}\right)=\frac{1}{2}S(N/2).\end{array}$$

(29)

Equation (27) is an example of the general constitutive Equation (5), where $N_L^{C{X}^{max}}$ plays the role of $Y^{C{X}^{max}}$. This equation has the following explicit form,

$$\begin{array}{c}\hfill {\left[{\Pi }_{j=1}^{N-N_L^{C{X}^{max}}}\left(1+\frac{N_L^{C{X}^{max}}}{j}\right)\right]}^2={\Pi }_{j=1}^{N/2}\left(1+\frac{N}{2j}\right),\mathrm{for}n=m=2.\end{array}$$

(30)

Just deriving Equation (30) (see Appendix C for details) is the primary purpose of this example. This is a transcendental equation of which the exact analytical solution is unknown. When deriving Equation (30), we used the initial condition for the entropy that is, $S(t=0)=S^{min}=ln\Gamma (N_L=N)=0$, which follows from Equations (24) and (25). Even for such a simple toy model, determining the partial measure of complexity is a non-trivial task, also because $N_L$ is different from $N/2$ (as we show below).

The numerical solutions of Equation (30), i.e., the relationship of $N_L^{C{X}^{max}}$ to N, are shown in Figure 8 (for simplicity, L defining the vertical axis on the plot means $N_L^{C{X}^{max}}$). Both of the solutions (small circles above and below the solid straight line) show that $N_L^{C{X}^{max}}$ is significantly different from $N/2$. Thus, the most complex state is significantly different from the equilibrium state.

Having the $N_L^{{CX}^{max}}$ dependence on N, we can obtain the dependence of the partial measure of specific complexity $c{x}^{max}\stackrel{\mathrm{def}.}{=}C{X}^{max}/N^{m+n}$ on N order $(m=2,n=2)$. We can write

$$\begin{array}{c}\hfill c{x}^{max}={\left(\frac{s(N/2)}{2}\right)}^4={\left[\frac{1}{2N}ln\left({\Pi }_{j=1}^{N/2}\left(1+\frac{N}{2j}\right)\right)\right]}^4,\end{array}$$

(31)

as in our case $s^{max}=s(N/2)$ equals the logarithm of the right-hand side of Equation (30) divided by N. Notably, Equation (31) is based on Equation (A12).

In Figure 10, we present the dependence of $c{x}^{max}$ on N. Quantity $c{x}^{max}$ is a non-extensive function—it reaches the plateau for $N\gg 1$. For $N\approx {10}^4$ the plateau is achieved with a good approximation. This is important for researching complexity. Namely, systems can attain complexity already on a mesoscopic scale. Although the absolute value of the complexity measure is relatively small, it is evident and possesses a structure that is related to the current inflection point there (near $N=10$).

This example shows that even such a simple arrangement of non-interacting objects may have non-equilibrium non-stationary complexity. A necessary (but not sufficient) condition is the possibility of constructing entropy and the presence of a time arrow.

4. Concluding Remarks

In many recent publications [5,8,9,51] it is argued that entropy can be a direct measure of complexity. Namely, a smaller value of entropy indicates more regularity or lower system complexity, while its larger value indicates more disorder, randomness and higher system complexity. However, according to Gell–Mann, more disorder means less, and not more, system complexity. These two viewpoints are contradictory—this is a serious problem, which we have addressed.

Our motivation in solving the above problem was based on Gell–Mann’s view of complexity. This is because we fail to agree that the loss of information by the system as it approaches equilibrium increases its complexity; notably, $\Delta I(p^{eq},p^{eq})$ (see Appendix B for detail) takes its minimum value then, and complexity must decrease.

In addition, the differences between entropies in Equation (1) eliminate the useless dependence of complexity on the additive constant that may appear in the definition of entropy. It can be said that the system state with the highest complexity is the state most distant from all of the states of the system of lesser or no complexity.

Thus, in the sense of Gell–Mann, the measure of complexity should supply complementary information to the entropy or its monotonic mapping.

Therefore, in this work, we have presented a methodology which allows building a universal measure of complexity as a function of a system state based on non-linearly transformed entropy. This is a non-extensive measure. This measure should meet a number of conditions/axioms, which we have indicated in this work. A parsimonious example, of the simplest system with a small and a large number of degrees of freedom, is presented in order to support our methodology. As a result of this approach, we have shown that (generally speaking) the most complex are optimally mixed states consisting of pure states, i.e., of the most regular and most disordered, which the space of states of a given system allows. This also applies to the distinctive examples outlined in Appendix D and Appendix E (although this requires a redefinition of some variables and parameters).

We should pay attention to an essential issue regarding the definition of the phenomenological partial measure of complexity that is given by the Equation (1). This definition is open in the sense that if the description of complexity requires, for example, one additional quantity, then the Equation (1) takes on an extended form,

$$\begin{array}{c}\hfill CX(S,E;m_1,n_1,m_2,n_2)\stackrel{\mathrm{def}.}{=}{(S^{max}-S)}^{m_1}{(S-S^{min})}^{n_1}{(E^{max}-E)}^{m_2}{(E-E^{min})}^{n_2}\ge 0,\end{array}$$

(32)

whereby $E^{min}\le E\le E^{max}$ this new quantity is marked. This definition has still an open character. Specifically, this definition also allows (if the situation requires) the replacement of one quantity with another, e.g., entropy with free energy, or considering some derivatives (e.g., of the type $\frac{\partial S}{\partial E}$). Openness and substitutability should be the key features of the measure of complexity. Moreover, exponents $m_j,n_j,j=1,2,$ determine the order of complexity, i.e., its level or scale. We emphasize that the measure of complexity introduced can describe isolated and closed systems (although in contact with the reservoir), as well as open systems that can change their elements.

From Equations (13) and (32), we get the phenomenological universal full measure of complexity in the form, which extends Equation (17),

$$\begin{array}{ccc}\hfill X(S,E;m_1^0,n_1^0,m_2^0,n_2^0)& \hfill =& {\left(1-\frac{1}{M_S}\right)}^2\frac{{(S^{max}-S)}^{m_1^0}}{1-\frac{S^{max}-S}{M_1}}\frac{{(S^{min}-S)}^{n_1^0}}{1-\frac{S^{min}-S}{M_1}}\hfill \\ \hfill & \hfill \times & \hfill {\left(1-\frac{1}{M_2}\right)}^2\frac{{(E^{max}-E)}^{m_2^0}}{1-\frac{E^{max}-E}{M_2}}\frac{{(E^{min}-E)}^{n_2^0}}{1-\frac{E^{min}-E}{M_2}}\ge 0.\end{array}$$

(33)

The full measure of complexity is a weighted sum of partial measures of complexity across all complexity scales. As one can see, this full measure may contain singularities. They are the necessary signatures of criticality existing in the system. This meets the expectations presented in the literature.

Definitions of measures of complexity Equations (1) and (17) and their possible extensions are universal and useful. It is due to entropy that is associated not only with thermodynamics (Carnot, Clausius, Kelvin) and statistical physics (Boltzmann, Gibbs, Planck, Rényi, Tsallis), but also with the information approach (Shannon, Kolmogorov, Lapunov, Takens, Grassberger, Hantschel, Procaccia), and with the approach from the side of cellular automata (von Neumann, Ulam, Turing, Conway, Wolfram, et al.), i.e., with any representation of the real world using a binary string. Today, we already have several very effective methods for counting entropy of such strings, as well as other macroscopic characteristics sensitive to organization and self-organizing systems, as well as to their synchronization (synergy, coherence), competition, reproduction, adaptation—all of them sometimes having local and sometimes global characters.

Our definition of complexity also extends to meet research into the complexity of the biologically active matter. In this, especially research on the consciousness of the human brain can derive a fresh impulse. The point is that most researchers believe that the main feature of conscious action is a maximum complexity or even a critical complexity [52]. In our approach, it would be $C{X}^{max}$ and $X\left(N_1^{cr}s\right)$.

We hope that our approach will enable: (i) the universal classification of complexity, (ii) the analysis of a system critical behaviour and its applications, and (iii) the study of dynamic complexity. All of these constitute the background to the science of complexity.