# Kolmogorov Complexity

**See:** Minimum Description Length Principle, Computer Program, Dataset's Kolmogorov Complexity, Lossless Compression.

## References

### 2013

- http://en.wikipedia.org/wiki/Kolmogorov_complexity
- In algorithmic information theory (a subfield of computer science), the
**Kolmogorov complexity**of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after the Andrey Kolmogorov who first published on the subject in 1963.Kolmogorov complexity is also known as "descriptive complexity" (not to be confused with descriptive complexity theory), Kolmogorov–Chaitin complexity,

**algorithmic entropy**, or program-size complexity.For example, consider the following two strings of length 64, each containing only lowercase letters and digits:

abababababababababababababababababababababababababababababababab

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7traquuxdppa0q7nieieqe9noc4cvafzf

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.More formally, the complexity of a string is the length of the shortest possible description of the string in some fixed universal description language (the sensitivity of complexity relative to the choice of description language is discussed below). It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself. Strings whose Kolmogorov complexity is small relative to the string's size are not considered to be complex.

The notion of the Kolmogorov complexity can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem.

- In algorithmic information theory (a subfield of computer science), the