In algorithmic information theory
(a subfield of computer science and mathematics),
the Kolmogorov complexity of an object, such as a piece of text,
is the length of a shortest computer program
(in a predetermined programming language)
that produces the object as output.
It is a measure of the computational resources needed to specify the object,
and is also known as algorithmic complexity,
SolomonoffKolmogorovChaitin complexity, program-size complexity,
descriptive complexity, or algorithmic entropy.
It is named after Andrey Kolmogorov, who first published on the subject in 1963.[1][2]
|