Complejidad de Kolmogórov

Detalle de una parte del conjunto de Mandelbrot. Almacenar esta imagen sin más en color de calidad 24-bit requeriría 1,62 millones de bits; sin embargo, una pequeño programa informática puede reproducir estos 1,62 millones de bits, usando la definición del conjunto de Mandelbrot. Por esa razón, la complejidad de Kolmogórov, es de hecho mucho menor que 1,62 millones de bits.

En la teoría de la computación, la complejidad de Kolmogórov es una medida de la cantidad de recursos computacionales necesarios para describir una cierta cantidad de información, debe su nombre a Andréi Kolmogórov. La complejidad de Kolmogórov también se denomina complejidad descriptiva o complejidad de Kolmogoróv-Chaitin, complejidad estocástica, o entropía algorítmica.

Para definir la complejidad de Kolmogórov, primero debe especificarse un lenguaje descriptivo para las secuencias o cadenas. Tal lenguaje puede basarse en cualquier lenguaje de programación como Lisp o Pascal. Si P es un programa que genera como outputs secuenciaas de tipo x, entonces P es una descripción del conjunto de x. La longitud de la descripción es la longitud de P como secuencia de caracteres. Para determinar la longitud de P, debe darse cuenta de las longitudes de todas las subrutinas empleadas en P. La longitud de cualquier número entero n que aparezca en el programa P es la cantidad de bits requeridos para representar n, esto es, log₂n.