Complexity is not entropy. So measure the structure, not the disorder.
Stir cream into coffee. It starts boring (cream on top, coffee below), becomes fascinating (cream pulled into thin tendrils and whorls), then turns boring again (uniform brown). Physics has a number that rises the whole time: entropy, the amount of disorder. But the thing we actually find interesting — the intricate structure — rises, peaks, and collapses. Entropy is monotone; interestingness is a hump. So whatever “interesting” is, it is not entropy.
Aaronson's bet: there is an honest, mathematical measure of that interestingness — one that is small at both ends and large in the middle. He builds it from algorithmic information theory, and adds one twist that makes it work for physical systems: it must count only structure that is hard to compress in a reasonable amount of time. He calls it complextropy.
Any honest measure of “interesting” has to be small for plain order, small for plain randomness, and large only for the structured mess in between.
The puzzle
Why does interesting structure appear, then vanish?
Step 1 · The running example
Cream in coffee: boring, interesting, boring again.
Here is the whole puzzle in one picture — and it's the picture we'll come back to on every step. Pour cream into black coffee and don't stir. Watch three moments in the mixing:
Entropy is the physicist's measure of disorder: roughly, the number of microscopic arrangements that look the same from far away. The Second Law of Thermodynamics says it only goes up in an isolated system — and in the cup it does, all three frames, monotonically. The uniform brown has the most entropy of all.
But nobody photographs the uniform brown and says “how intricate.” The structure we care about — the swirls — lives in the middle frame and is gone by the end. So the quantity we actually notice cannot be entropy. Naming and measuring that quantity is the whole problem.
Entropy rises monotonically; “interesting complexity” rises, peaks, then falls. The gap between those two shapes is the puzzle every later step is trying to close.
Aaronson: “even though isolated physical systems get monotonically more entropic, they don't get monotonically more ‘complicated’ or ‘interesting.’” The question was posed by Sean Carroll at the 2011 FQXi “Setting Time Aright” conference.
Step 2 · Two curves that disagree
Plot both over time: one climbs forever, one is a hump.
You've seen the three cups. Now put a number on each frame and plot it against time — entropy in one curve, “interesting structure” in the other. The whole post is the gap between these two shapes.
Here they are side by side. Read them left to right as the cup mixes:
So the design brief writes itself. We need a function of the cup's state that is small when everything is separated (you can describe it in a sentence: “cream on top”), small again when everything is uniform (“brown, evenly”), and large only when the cream is mid-swirl, where no short sentence captures the tangle.
The trap is that the obvious information-theory measure — Kolmogorov complexity, coming up next — fails this brief in a sneaky way. Fixing that failure is the heart of the post.
Small for plain order. Small for plain randomness. Large only for the structured mess in between. Any candidate measure lives or dies by whether it bends like the amber hump.
Entropy here is the ordinary thermodynamic / Shannon entropy of the cup's coarse-grained state. The amber “complexity” curve is exactly the quantity the post is trying to define rigorously — it is sketched, not yet computed.
The measure
Kolmogorov complexity · sophistication · and the resource-bound fix
Step 3 · Kolmogorov complexity
Measure a thing by the shortest program that prints it.
We need a measure that humps like the amber curve. The first honest candidate from information theory is Kolmogorov complexity — and seeing exactly how it fails is what points us to the fix.
The Kolmogorov complexity K(x) of a string x is “the length of the shortest computer program that outputs x” (in any fixed universal language — the choice barely changes the count). A string is simple if a tiny program prints it, complex if you basically have to spell it out. Let's compute it for three 1,000-bit strings by hand:
All order — “0000…0”
A thousand zeros. The program is “print 0 a thousand times.”
All randomness — a fair-coin string
1,000 coin flips. No pattern to exploit, so the shortest program is essentially the string itself, plus “print this.”
Structured mess — the tendrils
The mid-swirl cup: real structure, but tangled. Shorter than pure noise, longer than pure order — somewhere in the middle.
Rank them by K and the random string B wins — highest K of all. But B is the uniform brown coffee, the most boring end state. Plain Kolmogorov complexity rewards noise, exactly backwards from what we want. It climbs with entropy instead of humping.
The ~30-bit figure for A is illustrative (a short loop plus the count 1000). The key facts are exact: a random n-bit string has K ≈ n, and a perfectly regular one has K = O(log n). So K, like entropy, is highest for randomness.
Step 4 · Sophistication
Charge only for the structure bits — not the noise bits.
Plain K rewards noise. The fix, borrowed from algorithmic information theory, is to split a description in two and count only the half that describes genuine structure.
The trick is a two-part description. To pin down a string x, first name a set S that x belongs to (the “rules”), then say which member of S it is (the “label”). The cost of the rules is K(S); the cost of the label is about log₂|S|. Sophistication is the size of the rules only — the structure bits — at the point where x looks like a totally generic, random member of its own set:
soph(x)=min K(S)over S with x∈S, K(x|S) ≥ log₂|S| − c
read: the cheapest set of rules S that x sits inside as a typical, structureless member (c is a small fixed slack constant)
Separated cup: S = {that one string}, tiny rules, low sophistication. Uniform cup: S = {all brown-ish states}, also tiny rules (“anything goes”), low sophistication. Only the tendril cup needs elaborate rules to describe — high sophistication. The hump is back.
Sophistication is due to Koppel and to Gell-Mann & Lloyd's related “effective complexity.” Condition K(x|S) ≥ log₂|S| − c is the formal way of saying “x is a generic member of S” — it carries no extra structure beyond belonging to S.
Step 5 · The loophole
For a deterministic system, “initial state + clock” is a cheat code.
Sophistication humps for strings — beautiful. But plug in a real physical system evolving in time and a loophole opens that flattens the hump back out. Spotting it is what forces the final ingredient.
Suppose the coffee cup is deterministic: the same starting state always evolves the same way. Then there is a maddeningly short description of the cup at any time t — “take the initial state, run physics forward for t steps.” The initial state is a constant number of bits; the clock value t costs only log(t) bits. So whatever the swirls look like, you can name the whole state cheaply.
Because that description is allowed to take astronomically long to run, it counts as “short.” Sophistication only sees its length, ~log(t), and stays low the whole time. To rescue the hump we must forbid the cheat code — by limiting how long the program may run.
Aaronson's words: the state “can always be specified by giving (1) the initial state, and (2) the number of steps t.” The first is O(1) bits, the second log(t) — so unbounded sophistication rises “at most logarithmically with t.”
Step 6 · Complextropy
Add a stopwatch to sophistication — and the hump comes back.
The loophole was that the “short” description was allowed to run forever. Aaronson's fix is one word long: fast. Demand that every program in the definition run quickly — and the cheat code is outlawed.
Complextropy is sophistication with a resource bound. Roughly: the length of the shortest program that runs in about n·log(n) time and samples a near-uniform member of a set S that x belongs to — where even the reconstructor is held to that same time budget. The exact bound is arbitrary; what matters is that it is severe enough to ban “simulate physics for t steps.”
Drag time — watch entropy climb forever while complextropy humps
Grey only ever rises. Amber goes up, then down. Slide to the far left or far right and complextropy is low — plain order, plain randomness. Park it in the middle and complextropy peaks: that's the tendril cup.
The marker rides the amber hump, not the grey line. Complextropy is the curve we wanted all along — small at both ends, large in the middle. Heights are illustrative; the shape is the claim.
Here is the definition in symbols. Treat it as relief, not new difficulty — it just says “shortest fast program that samples a set x is a generic member of”:
complextropy(x)=min |P| : P runs in n·log n time, samples S ∋ x uniformly
…and any equally-fast program reconstructing x from S-samples still needs ≥ log₂|S| − c bits (so x stays a generic member of S, now under a time budget)
Complextropy = sophistication, but only structure that is hard to compress quickly counts. The slow “simulate from the start” description no longer qualifies, so the deterministic loophole is closed and the hump survives.
“n·log(n) is just intended as a concrete example of a complexity bound,” and it “doesn't even matter much what kind of resource bound we impose, as long as the bound is severe enough.” The constant c is a fixed slack and never gets a numeric value.
The conjecture
The First Law · a gzip experiment you can run · and why it matters
Step 7 · The First Law of Complexodynamics
The claim, stated plainly: complextropy is low, high, then low.
You now have a measure that humps for strings and survives the deterministic loophole. The post's actual conjecture is the obvious next sentence — and naming it gives the post its title.
The First Law of Complexodynamics (Aaronson's tongue-in-cheek name): for a closed system that mixes, complextropy is “small for the initial state, large for intermediate states, then small again once the mixing has finished.” In coffee terms: boring, fascinating, boring. The measure traces the amber hump you just dragged.
Aaronson is candid: “I don't yet know how to prove this conjecture.” He frames it not as an open-ended musing but as “a relatively bounded question about which actual theorems could be proved and actual papers published.” The value is in sharpening the question.
He also rules out a tempting alternative: Charles Bennett's logical depth (the runtime of the shortest program). Once you fix the boundaries, sampling a micro-state is nearly linear-time — so depth “need not become large at any point during the mixing.” Depth doesn't hump; complextropy is meant to.
Step 8 · The gzip experiment you can run
Can't compute complextropy? Compress the snapshots and watch.
The conjecture is clean but complextropy, like Kolmogorov complexity, is uncomputable in general. Aaronson's escape hatch makes the whole idea testable on a laptop — and it's delightfully low-tech.
Swap the uncomputable measure for one you can compute: the size of a gzip-compressed file. A real compressor finds short descriptions in bounded time, so it's a rough stand-in for a resource-bounded one. Take snapshots of a simulated mixing system, gzip each, and plot the file sizes over time. If the First Law holds, the sizes should trace the same low-high-low arc. Step through the three snapshots:
Advance the snapshot and read its gzip size — does it hump?
Snapshot t = 0 (separated). gzip size is small — a one-line rule describes it.
The middle snapshot compresses the worst — its bar is the tallest. Separated and uniform cups each have a short rule (“cream on top” / “brown, evenly”), so they gzip small. The tendrils have no short rule, so they gzip large. The proxy humps. Sizes are illustrative of the predicted shape.
gzip is fast and finds genuine structure, so it behaves like a resource-bounded description — exactly the flavour complextropy needs. It can't see deep mathematical structure a slow algorithm might, but for “does interesting structure rise then fall?” it's a reasonable first probe.
Aaronson's suggestion: estimate complextropy “by using something you can compute (e.g. the size of a gzip compressed file).” An MIT undergrad, Lauren Ouellette, began exactly this project with him — which, three years later, grew into the “Coffee Automaton” paper that ran the experiment in earnest.
Step 9 · Where it stands & recap
A sharpened question — and can you now explain it?
You've seen the puzzle, the failed measure, the fix, the conjecture, and the laptop experiment. Final question: how settled is all this, and have you actually got it?
Status card · what is and isn't established
The puzzle · entropy ≠ complexity
The measure · complextropy defined
The First Law · low–high–low
Empirical proxy · gzip the snapshots
Now you can explain it. Five questions — answer each out loud before opening it. If all five come easily, you've genuinely got this post.
Why isn't entropy the right measure of “interesting”?
Entropy only ever rises, so it's highest for the uniform brown coffee — the most boring frame. Interesting structure peaks in the middle and is gone by the end. A measure that climbs monotonically can't trace a hump.
Why does plain Kolmogorov complexity fail too?
K(x) is the shortest program that prints x, so a fully random string scores highest — but that's the uniform end state. Like entropy, K rewards noise. We need to count structure bits, not noise bits.
What does sophistication add?
It splits the description into a set S (the rules) plus a label (which member). Sophistication counts only K(S), the rules, when x is a generic member of S. Both pure order and pure randomness need trivial rules, so both score low — the hump appears.
Why add a resource bound to get complextropy?
For a deterministic system you can describe any state by “initial state + run for t steps” — only log(t) bits, so sophistication stays low forever. Requiring programs to run fast (≈ n·log n) outlaws that slow cheat, and the hump survives.
How would you test the First Law without a proof?
Replace the uncomputable measure with gzip. Snapshot a simulated mixing system, compress each frame, and plot the file sizes. If they go small, large, small over time, the conjecture survives its first empirical check.
What happened next — the gzip idea wasn't idle. Aaronson and Lauren Ouellette, joined by Sean Carroll, built a concrete “coffee automaton” lattice model, ran the compression experiment, and reported that a smoothed complexity measure does rise and fall while entropy climbs — turning the blog conjecture into a 2014 paper.
“Even though isolated physical systems get monotonically more entropic, they don't get monotonically more ‘complicated’ or ‘interesting.’” — Scott Aaronson, 2011
A masterclass in asking the right question.
This post proves nothing. Its lasting value is the move it models: take a fuzzy intuition — “why does interesting stuff appear and then vanish?” — and carve it into something a theorem could one day settle.
The Coffee Automaton
Aaronson, Carroll & Ouellette built a lattice model, ran the gzip experiment, and showed a complexity measure that rises and falls while entropy climbs.
Frame, then prove
Borrowing sophistication and adding a resource bound turned a cocktail-party question into “a bounded question about which actual theorems could be proved.”
Ilya's 30u30
It earned a spot on Ilya Sutskever's foundational reading list — not for an answer, but as a model of how to sharpen a question worth answering.
Entropy measures how disordered a system is; complextropy tries to measure how interesting it is — and that distinction is the whole point.