Complejidad de Kolmogórov

Debe su nombre a Andréi Kolmogórov.

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 salidas secuencias de tipo x, entonces P es una descripción del conjunto de x.

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, log2n.

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, un pequeño programa informático 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.