Sitemap
Press enter or click to view image in full size

What Is Complexity?

Overview of Complexity Measures
Many different quantities have been proposed to measure what we mean by “complexity” (and its opposite, simplicity). Some measures, like computational complexity, focus on time or space — essentially, how long or how much memory a standard computer would need to perform a task or carry out a computation. Others are based on information theory and look at the length of the shortest message (or program) needed to describe something. For instance, the algorithmic information content (AIC) of a bit string is defined as the length of the shortest computer program that can output that string and then stop.

Context and Subjectivity
When we try to apply these measures to real-world objects or systems, they become somewhat subjective. They depend on how we describe the entity (the level of detail), our background knowledge, the language and coding method used, and even the choice of the standard computer. However, if we compare similar entities as they grow larger, many of these arbitrary factors become less significant. In computer science, for example, we often care whether the time needed to solve a problem increases polynomially with its size rather than exponentially.

Uncomputability and the Limits of AIC
A challenge with measures like AIC is that they are generally uncomputable. Even if we know an upper bound for the AIC of a string, we cannot always be sure there isn’t a shorter description hiding somewhere. A completely random bit string is considered “incompressible” because it lacks any regular patterns, meaning its AIC is as high as possible for its length. This leads to the idea of algorithmic randomness. However, this approach does not align with our everyday sense of complexity. For example, Shakespeare’s works have a lower AIC than random noise, even though we intuitively consider Shakespeare’s writing to be more complex.

Effective Complexity
A more useful measure in everyday language is effective complexity. Rather than just looking at the shortest description of something, effective complexity considers the length of the shortest description of its regularities or patterns. In other words, a completely random sequence (with almost no regularities) would have low effective complexity, as would a perfectly regular (and simple) sequence. High effective complexity is found only in things that lie between complete order and complete chaos.

Finding Regularities
Although it is impossible to identify every regularity in an entity, we can usually find important classes of them. A common approach is to break a piece of data (say, a bit string) into parts and measure the shared information between these parts. If the shared information (or mutual algorithmic information) exceeds a certain threshold, we consider that a meaningful regularity. The effective complexity is then measured by the AIC needed to describe these regular patterns.

Get JUNAID’s stories in your inbox

Join Medium for free to get updates from this writer.

The Role of Adaptive Systems
In many cases, regularities are not identified by an outside observer but by the system itself. Consider complex adaptive systems — systems that learn, evolve, or otherwise adjust to their environment. Examples include biological evolution, human learning and thinking, the immune system, scientific research, and even certain computer models like neural networks or genetic algorithms. These systems continually identify and compress regularities in the data they receive, using internal models (or “schemata”) to predict and adapt to future events. This process is subject to errors and requires significant computation, which brings in additional measures like logical depth (the time needed to generate or reproduce a pattern) and crypticity (the time required to reverse-engineer a pattern).

Logical Depth and Crypticity

  • Logical depth reflects how much time a computer would take to compute a pattern from a compressed description.
  • Crypticity is the reverse: it measures how long it would take to deduce a concise description from the pattern.
    In scientific work, crypticity can be thought of as the challenge of developing a theory from data, while logical depth relates to how hard it is to use that theory to make predictions.

Effective Complexity vs. Logical Depth
Sometimes what looks complex at first glance is actually simple if you know the underlying rule. For example, the detailed image of a fractal might seem highly complex, but if it is generated by a very simple formula, its effective complexity is low — it merely has logical depth due to the calculations needed to produce it.

The Universe and Complexity
Modern physics suggests that the fundamental laws of the universe (for example, those described by quantum field theory or even superstring theory) are relatively simple. Even the initial conditions of the universe might be simple. However, the unfolding history of the universe is not predetermined. Because quantum mechanics only provides probabilities for events, chance plays a huge role in shaping complexity over time.

As the universe evolves, countless random events (or frozen accidents) accumulate. While many of these random events have little impact, some lead to significant, lasting regularities in the structure of matter and energy. The majority of the effective complexity in the universe arises from these accumulated events rather than the basic laws of physics alone.

Potential Complexity
Finally, because events continue to unfold, we introduce the idea of potential complexity — a measure of how much effective complexity an entity might have in the future, based on probabilities over various possible histories. Even though local systems may sometimes become simpler or more disordered, the overall potential for complexity in the universe tends to increase with time.

JUNAID
JUNAID

Written by JUNAID

Research Scholar (Data Science)