Complexodynamics

Here's a puzzle that hides in plain sight: entropy increases monotonically, but complexity doesn't. A coffee cup starts simple (black coffee, white milk, separated). It ends simple (uniform beige). But in between, when the milk is swirling in tendrils through the coffee, something is at a maximum — and it isn't entropy. The same pattern holds for the entire universe. Shortly after the Big Bang: a simple, hot, low-entropy soup. A googol years from now: a simple, cold, high-entropy soup. Right now: galaxies, brains, hot-dog-shaped novelty vehicles. What is that peak in the middle, and why does it happen?

Sean Carroll posed this question at a 2011 conference, and Scott Aaronson sketched a possible answer using ideas from Kolmogorov complexity theory. What makes Aaronson's proposal interesting isn't just the answer but the way it reveals that "complexity" is a harder concept than anyone casually using the word tends to realise.¹

The Problem with Defining Complexity

The obvious first move is to use Kolmogorov complexity — the length of the shortest computer program that outputs a given string. But this fails immediately for deterministic systems. If the system's dynamics are deterministic, you can always specify the state at time t by giving (1) the initial state, (2) the transition rule, and (3) the number t. The initial state and rule are constant; t takes log(t) bits. So the Kolmogorov complexity grows at most logarithmically, no matter how visually complex the state looks. This is a genuinely surprising failure — it means that formal "complexity" and intuitive "interestingness" come apart completely for deterministic systems.¹

You can partially fix this by switching to probabilistic systems (where Kolmogorov complexity does grow polynomially) or by imposing resource bounds — requiring that the program not just output the state, but do so quickly. Resource-bounded Kolmogorov complexity makes the simple-looking initial states genuinely simple and the visually complex intermediate states genuinely hard to produce in bounded time.

But even resource-bounded Kolmogorov complexity doesn't do what Carroll wants. It increases with time and then... keeps increasing. It doesn't come back down. The equilibrium state — uniform beige coffee — is hard to distinguish from random noise, and random noise has high Kolmogorov complexity. We need something that's low for simple states, high for complex intermediate states, and low again for random states.

Sophistication: Neither Simple Nor Random

The tool that works — or at least, that Aaronson conjectures works — is a concept called sophistication, introduced by Kolmogorov himself in the 1970s and formalised by others since. The idea is ingenious: instead of asking "how short is the shortest program that outputs x?", ask "how short is the shortest program that outputs a set S of which x is a typical random member?"¹

If x is simple (like all zeros), then S can be the singleton set {x} — tiny to describe. If x is uniformly random, then S can be the set of all strings of that length — also tiny to describe. But if x has intricate structure that's neither trivially simple nor generic-random — like the tendrils in the coffee cup — then any set S of which x is a "random" member must itself be structurally complex, and describing S takes many bits.¹

This is a beautiful idea, and it captures something real about what we mean by "complex." A crystal is simple (low sophistication). White noise is simple (low sophistication). A city, a genome, a turbulent fluid — these are neither crystalline nor random, and describing the class of things they're typical of requires genuine structural information.

The Computational Twist

But raw sophistication still doesn't solve Carroll's puzzle, for the same reasons Kolmogorov complexity didn't: in a deterministic system, you can always specify S as "the set of all states reachable from this initial condition in exactly t steps," and that description is short regardless of how complex S looks.

Aaronson's solution is to impose computational resource bounds in two places simultaneously. Define "complextropy" as the length of the shortest efficient program that samples from a set S such that (1) x is in S, and (2) no efficient algorithm can reconstruct x from random samples of S using fewer than log₂|S| bits. Both the sampling algorithm and the reconstruction algorithm must be computationally bounded.¹

Why two bounds? Without the first, the sampling algorithm could generate exactly the right set S by simulating the full dynamics — and that set is cheaply described. Without the second, an unbounded reconstruction algorithm could exploit subtle structural features to compress x well beyond what the set size predicts. The double bound is what produces the desired behaviour: low at early times (the state is simple), high at intermediate times (the state has structure that's hard to describe efficiently), low again at late times (the state is generic enough that efficient algorithms can't distinguish it from random).¹

What This Gets Right and What's Missing

Aaronson is admirably honest that this is a conjecture, not a theorem. Nobody has proved that "complextropy" actually peaks at intermediate times in any natural model system. He proposes a concrete test: simulate a 2D "coffee cup" (a grid of black and white pixels with random nearest-neighbour mixing) and try to plot the complextropy over time. The prediction is that it peaks when the boundary between mixed and unmixed regions is maximally irregular.¹

The deeper issue is that complextropy, under any reasonable definition, is almost certainly intractable to compute. You'd have to approximate it using something like gzip compression as a rough substitute — a standard hack in Kolmogorov complexity research, but one that sweeps a lot of subtlety under the rug.

Still, the conceptual picture is compelling. The second law of thermodynamics tells us entropy increases. Complexodynamics — if it works — tells us that structure rises and falls, peaking when a system is far enough from its initial conditions to be non-trivial but not yet close enough to equilibrium to be generic. This is the regime where interesting things happen: where Emergence produces patterns that are neither designed nor random, where Cellular Automata generate structures that resist simple description, where life exists.

The connection to information and computation is direct. If complexity is best understood through computational resource bounds — not just information content but computational difficulty — then the physics of complex systems is inseparable from the theory of computation. Aaronson's proposal suggests that the reason the universe is interesting right now is a consequence of computational complexity theory, not just thermodynamics. That's a bold claim, and it's far from proven, but it's the kind of claim that makes you want to see the proof.