Linked from

The 16 pages that link to Kolmogorov complexity, each with the reason it gives.

• Information theoryCompared with: It offers an individual-string notion of information distinct from Shannon’s statistical averages.

• Claude ShannonCompared with: It offers an individual-object notion of information distinct from Shannon’s statistical measure.

• Computability theoryRelated: Its exact values are generally uncomputable, linking information measurement to algorithmic limits.

• Data compressionRelated: It gives a theoretical notion of compressibility based on the shortest description.

• Andrey KolmogorovBroader topic: Kolmogorov defined randomness through the incompressibility of individual objects.

• Lossless compressionRelated: It describes an ideal, uncomputable notion of how much a particular file can be compressed.

• Computable functionRelated: Its uncomputability reveals limits on measuring the simplest effective description.

• Leonid LevinRelated: Levin’s work links universal computation and description length to algorithmic information.

• Unary numeral systemRelated: Unary descriptions show how representation choices affect the measured length of number-encoding programs.

• Algorithmic information theoryBroader topic: It is the central measure of description length in algorithmic information theory.

• Minimum description lengthRelated: MDL uses computable codes to approximate this ideal measure of description length.

• Vladimir ArnoldCompared with: Despite the shared name, this theory is associated with Andrey Kolmogorov, not Arnold.

• Blum's speedup theoremCompared with: It measures program description length, unlike Blum measures of computational cost.

• Blum axiomsCompared with: Unlike standard Blum measures, its bounded-value test is generally undecidable.

• Infinite monkey theoremRelated: A target's complexity helps quantify how unlikely it is to appear in a short random sample.

• Information and communication theoryCompared with: Unlike Shannon entropy's average uncertainty over a distribution, it measures individual descriptions.