![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Mandelpart2_red.png/640px-Mandelpart2_red.png&w=640&q=50)
Complejidad de Kolmogórov
De Wikipedia, la enciclopedia encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Mandelpart2_red.png/640px-Mandelpart2_red.png)
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, log2n.