02 junio 2007

Complejidad de Kolmogorov

La complejidad de Kolmogorov de una cadena S es el tamaño de la menor cadena de texto que permite definir S.

Tenemos esta cadena de 64 digitos:

S = 01010101010101010101010101010101
01010101010101010101010101010101

Se puede definir así: "escribe 32 veces 01". Tiene 19 letrás y por tanto el valor de la complejidad es 19.
K(S) = 19

Sin embargo esta cadena ¿cómo podría definirse?

S2 = 11001000011000011101111011101100
11111010010000100101011110010110

La mejor manera de definir esta cadena es símplemente escribir la cadena entera, por tanto:
K(S2) = 64.

Ninguna cadena puede tener un K mayor a su tamaño.

Las cadenas que tienen una K igual a el tamaño de la cadena original se llaman complejas. Porque no se conocen formas eficientes de definirlas.

Por ejemplo, que cuesta menos: ¿escribir los 1000 primeros números enteros o un programa en Python que cuando lo ejecutes te imprima los 1000 primeros números enteros?.

Imagina que quieres mandar todo tu disco duro a un amigo por el messenger, ¿podrías escribir un programa corto en algún lenguaje de programación que al ejecutarlo diera como resultado todo el contenido de tu disco duro? Se podría decir que ese programa sería todo tu disco duro "comprimido".

Bienvenidos al maravilloso mundo de la Algorithmic complexity theory. Dicen que es muy útil para ciertas cosas... yo pienso que...