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

En la teoría de la computación, la complejidad de Kolmogórov es el tamaño o cantidad de información del programa de computadora más corto que produce cierto resultado. 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 salidas secuencias 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.

Véase también

• Teoría algorítmica de la información
• Teoría de la complejidad computacional

Enlaces externos

• Comparación de códigos generadores del conjunto Mandelbrot en RosettaCode.

• Datos: Q1456811
• Multimedia: Kolmogorov complexity / Q1456811