Kolmogorov Complexity

The Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. ( a.k.a. descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity.)

For example, consider the following two strings of length 64, each containing only lowercase letters, numbers, and spaces:


The first string has a short English-language description, namely "ab 32 times", which consists of 11 characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has 64 characters.

The complexity of a string is the length of the string's shortest description in some fixed universal description language. Strings whose Kolmogorov complexity is small relative to the string's size are not considered to be complex. The notion of Kolmogorov complexity is considered surprisingly deep and can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem.

If a description of s, d(s), is of minimal length—i.e. it uses the fewest number of characters—it is called a minimal description of s. Then the length of d(s)—i.e. the number of characters in the description—is the Kolmogorov complexity of s, written K(s). Symbolically,

K(s) = |d(s)|. \quad