skip to content

If Kolmogorov complexity is the length of the shortest program printing a file, why is a compressed size only an upper bound?

level: middleimportance: should knowfreq 40%

answer

  1. a property of the string, not the tool
  2. shortest description, not smallest output
  3. decoder plus payload is a program
  4. the inequality runs one way
  5. existence proves at most, never at least

basics

~20 s

Kolmogorov complexity is the length of the shortest program that outputs a string. A decoder plus its payload is one such program, so it bounds the complexity from above. Nothing a coder fails to do bounds it from below.

solid answer

~40 s

Fix a description language. The Kolmogorov complexity `K(s)` of a string is the length in bits of the shortest program in that language that takes no input, writes `s`, and halts. Any lossless coder hands you a concrete program: the payload `c(s)` plus the decoder `D` that turns it back into `s`. So `K(s) <= |c(s)| + |D| + O(1)`, and `|D|` is a fixed cost that does not grow with the input. That is an upper bound in one direction only. Producing a program proves a short description exists; failing to shrink a file proves only that the coders you tried found no structure in it. Quoting a compressed size as the file's information content drops the decoder from the description and assumes the coder was optimal.

go deeper

for a junior

Remember the one-sentence definition: the shortest program that prints the string. Also remember that the size a compression tool achieves is an estimate of that, not the thing itself.

for a middle

Be able to build the bounding program out loud - payload plus decoder plus glue - and state the inequality in the right direction, including why the decoder size is a fixed cost that stops mattering as inputs grow.

for a senior

Show where the distinction changes a decision: density benchmarks compare coder-and-data pairs, and a claim that a payload has reached its minimum needs the coder named and the decoder counted.

for a principal

The trade-off you own is what an unmeasurable quantity may be used to justify. Decide which claims your teams may base on a compression ratio, and insist that the measured program, decoder included, is what gets reported.

## What the measure actually is Fix a **description language**: any notation powerful enough to express an arbitrary computation, together with an interpreter that runs it. The **Kolmogorov complexity** `K(s)` of a finite string `s` is the length, in bits, of the shortest program in that language that takes no input, writes `s`, and halts. Nothing else about that program counts - not its running time, not its memory use, not whether any human or search procedure could ever find it. Two consequences follow at once, and both are easy to state and easy to forget: - `K(s)` is a property of **the string**, not of any tool. A file does not 'compress well' as an intrinsic trait; a particular coder does or does not find structure in it. - `K(s)` is about the **existence** of a short description. It is silent on whether that description is discoverable, and on how much work finding it would take. This is a different kind of quantity from one defined over a probability distribution of messages, which asks how many bits a source needs on average. Descriptive complexity asks about one concrete string, with no source and no distribution in sight. ## Why a coder hands you an upper bound for free Run any lossless coder over `s`. You get a payload `c(s)`, and you already possess the decoder `D` that turns that payload back into the original. Glue them together: a program that carries `c(s)` as literal data, hands it to `D`, and prints the result. That program outputs `s` and halts, so by definition it cannot be shorter than the shortest such program: ``` K(s) <= |c(s)| + |D| + O(1) ``` The `|D|` term is the size of the decoder and the `O(1)` is the fixed glue; neither grows with `s`, because the same decoder serves every input. For large inputs the payload dominates, which is why quoting a compressed size is a **usable estimate** even though it is not the quantity itself - it can coincide with `K(s)` only by accident, and you can never tell when it has. What matters is the direction. You produced a program, and a program's existence bounds the minimum **from above**. To bound it from below you would have to show that *no* program shorter than some length prints `s` - a claim about every program, which no amount of running one coder can establish. | What you observed | Sound conclusion | The tempting error | |---|---|---| | 1 GB shrinks to 4 MB, decoder is 200 KB | `K` is at most about 4.2 MB | 'the content is exactly 4 MB' | | Three strong coders all fail on it | Those three found no structure | 'the file is incompressible' | | A newer coder gets it to 1 MB | The upper bound falls to about 1 MB | 'its complexity went down' | | Coder A beats coder B here | A models this data better | 'A measures complexity more accurately' | The third row is where people trip: the number you can compute moves, and the number you cannot compute never did. ## Count the whole description, not just the payload A bound is only a bound if the program you described is complete. Anything the decoder needs in order to reproduce `s` belongs in the count: 1. **The decoder itself.** A 200 KB decoder is noise next to a gigabyte and decisive next to a kilobyte - which is why 'this 40-byte record compressed to 12 bytes' means nothing on its own. 2. **Any model or dictionary** the coder learned or was preloaded with. Training a dictionary on the corpus and then reporting the payload alone moves bits out of the measurement instead of removing them from the data. 3. **Any decode parameters** - window sizes, table layouts, block boundaries - unless they are fixed constants baked into every copy of the decoder. ## Where the distinction bites at work - A density benchmark measures a **coder-and-data pair**, never the data alone; two teams reporting different ratios on the same corpus are both right about different programs. - 'We might find a better encoding later' is always safe as a claim about the bound: the upper bound can only fall as descriptions improve, so an encoding win never contradicts an earlier measurement. - An upper bound is still actionable. It certifies that a cheap representation exists and that you are holding one, which is exactly what a storage or transfer decision needs. - When someone reports that a payload is 'already at its theoretical minimum', the honest questions are: minimum under which coder, and is the decoder in the number?

  • Does the upper bound still hold when the coder trains a model or dictionary on the data first?
    Yes, but only if you count it. The trained model is data the decoder needs, so the honest bound is payload plus model plus decoder. Reporting the payload alone describes a program that could not actually reproduce the file, and a quantity that no longer bounds anything.
  • If compressed size is an upper bound, what would a lower bound on a specific string's complexity require?
    A proof that no program below some length prints it - a statement about all programs, not about the ones you ran. General counting results say that almost every string of length n needs close to n bits, but that is a statement about the population, not a certificate you can attach to a named file.

saying these in an interview costs you the question

  • Says a file's compressed size is its Kolmogorov complexity
  • Leaves the decoder out of the description being measured
  • Treats one coder's failure as proof the string is incompressible
  • Thinks a better coder pushes a file below its true complexity
  • Describes complexity as a property of the tool rather than the string
  • Reports a payload size after training a dictionary on the same data