El concepto de complejidad es muy interesante.
Prácticamente todo el mundo tiene una idea intuitiva de lo que significa que algo es "complejo", pero definir de manera clara y sin equívocos que algo es más complejo que otra cosa.
En parte esto viene del hecho de que la palabra "complejidad" se puede aplicar a muchos campos.
Como ejemplo en este diagrama viene la evolución del término con el tiempo:
Entonces, si es algo que se aplica a tantos campos ¿se puede definir?
Pues la respuesta es obvia, para cada campo hará falta una definición diferente.
En la tesis doctoral [1] de la doctora Sheila López, profesora en la Universidad de Sevilla y experta en estos temas, se pueden
ver algunas de las definiciones de complejidad.
• Formulaic complexity: Descriptive (length of account that must be given to provide an adequate description of the system), algorithmic (the length of the system instructions) and computational (the time required to solve a problem) complexities.
• Compositional complexity: Constitutional (number of parts or components) and taxonomical (numbers of different kinds of components in the physical configurations of the system) complexities.
• Structural complexity: Organizational (number of different ways of arranging components in different modes of interrelationship) and hierarchical (organizational disaggregation into subsystems) complexities.
• Functional complexity: Operational (variety of modes of operation) and nomic (degree of elaboration of the laws which govern a phenomena) complexities.
Y ahora, como es inteligente empezar por el principio comenzaremos con la definición de complejidad más antigua y famosa de todas, la de Kolmogorov.
COMPLEJIDAD DE KOLMOGOROV
La complejidad de Kolmogorov es sin duda la definición más famosa de complejidad de todas. Aunque pueda parecer extraño se aplica a un sistema muy concreto, una cadena de caracteres.
Básicamente viene a decir la complejidad de una cadena de caracteres es igual al programa más corto que es capaz de generarla. Vamos a ver un ejemplo, la siguiente cadena de caracteres:
101010101010101010101010
Esta es a todas luces una secuencia muy sencilla, ¿no?
Un programa que la generase sólo tendría que repetir el patrón las
veces que haga falta.
En el lenguaje de programación C, por ejemplo, sería:
for (i=0;i<12 font="font" i="i" printf="printf">
Ahora veamos otra lista de caracteres:
vwrtgw45g238g23e823hr3928ry
Esta al no seguir ninguna regularidad no es tan fácil de programar, de hecho tienes que hacer un programa que sepa la lista en si y la escriba, algo en plan
printf("vwrtgw45g238g23e823hr3928ry")
Ambos programas son similares en tamaño, pero tienen una diferencia muy importante: Si la cadena crece el primer programa se queda casi igual, pero el segundo depende directamente del tamaño de la cadena.
Eso demuestra que la segunda cadena es más compleja que la primera, porque su complejidad depende de su tamaño, y en la primera no.
Ahora bien. ¿Tiene sentido medir la complejidad de una cadena de caracteres? ¿A quién en su sano juicio le importa eso?
Pues no se nos debe olvidar que en cadenas, o matrices, de caracteres se almacena la información, como los dibujos o las fotos.
Un ejemplo clásico es el siguiente:
¿Dirían que el siguiente dibujo es o no complejo?
La respuesta es simple: No mucho.
Este dibujo pertenece a un Conjunto de Mandelbrot, que se puede generar a partir de una fórmula muy sencilla.
Por otra parte si lo queremos más grande tampoco necesitamos ampliar el programa, sólo cambiarle los bordes.
Así pues este bonito dibujo tiene muy poca complejidad.
¿Y cómo ven la siguiente figura?
Esta no se me ocurre ninguna manera de generarla que no sea dar la figura en sí. Tampoco se me ocurre como saber que hay más allá de lo que se muestra sin dar la información en si.
Así que este sí es una figura con una alta complejidad de Kolmogorov.
El problema con esta medida es el siguiente.
Siempre una cadena aleatoria dará el mayor valor de complejidad, porque al ser aleatoria no se puede hacer un programa que la genere salvo que de los datos uno a uno.
Esto hace que muchos consideren la complejidad de Kolmogorov más como una medida de aleatoriedad que de complejidad.
Además, dentro de la aleatoriedad tampoco hace distinciones.
Vamos a ver esto último con más profundidad, porque dará
lugar a la siguiente parte.
La cuestión es que la separación entre aleatorio y determinista es bastante arbitraria. Los procesos aleatorios no son todos iguales y dependen de la función de distribución que los controla, sin embargo la complejidad de Kolmogorov le asocia a todos un valor máximo.
Por otro lado, un proceso determinista también se puede definir como un proceso aleatorio con una distribución determinada
(la llamada Delta de Dirac). Para analizar esto se crearon otras medidas que vamos a mostrar ahora.
MEDIDAS ESTADÍSTICAS DE COMPLEJIDAD
La idea de estas medidas estadística es simple, no todas los procesos aleatorios (o lo que es lo mismo, no todas las distribuciones de probabilidad) son iguales.
Entonces ¿Cuáles son más complejas que cuales?
Pues para eso hay que establecer un mínimo, es decir, hay que decir que distribuciones son las menos complejas.
El acuerdo general es que las distribuciones menos complejas son la totalmente uniforme, en la que todo puede ocurrir con la misma probabilidad, y la determinista, donde está ya escrito lo que va a pasar.
La idea se puede entender con el siguiente dibujo:
A la izquierda tenemos un caso que representa el determinismo, en este ejemplo un cristal. Los átomos del cristal están ordenados y sólo pueden ocupar un sitio definido, dando lugar a un sistema poco complejo, porque es fácil de describir.
A la derecha tenemos el caso opuesto, un gas perfecto en una caja.
Si tomamos un trozo del centro de la caja (para poder omitir la interacción con las paredes de la caja) cualquier posición es igual a las demás y un átomo puede estar en cualquier parte con la misma probabilidad, así pues este sistema también se considera poco complejo.
En medio tenemos un caso más complicado, una cadena de ADN.
En el ADN las posiciones no están tan definidas como en el cristal, porque
se puede plegar, es flexible y demás, sin embargo tampoco es totalmente aleatoria como en el caso del gas.
Este es un ejemplo de un sistema complejo.
A partir de esta idea tan simple se crearon distintas medidas de complejidad, como la LMC, la Fisher-Shannon y otras.
El único problema es que la definición es muy abierta, y hay un sinfín de medidas que den mínimo valor para esas distribuciones.
Sin embargo, con paciencia bastantes investigadores han ido aplicando estas medidas a sistemas como átomos y moléculas,
con resultados bastante inesperados.
Para una información más técnica se puede leer la tesis que ya cité [1]
o la mía, de paso [2].
En un post futuro, pero no muy lejano, hablaré de como estas medidas se alican en el campo de la física cuántica.
Bibliografía
[1] Information-theoretic measures of atomic and molecular systems.
Tesis Doctoral. Sheila López Rosa.
[2] Information and Entanglement Measures in Quantum Systems With Applications to Atomic Physics. D. Manzano. http://arxiv.org/abs/1103.3186
