La complejidad de un programa

Una vez conocí a una mujer que había leído un libro sobre recursos mnemotécnicos y, según parece, lo había malinterpretado completamente. Para memorizar un número de teléfono, por ejemplo, quizá tenía que recordar que su mejor amiga tenía 2 hijos, su dentista tenía 5, su compañera de piso en la universidad 3, su vecino de la derecha tenía 3 perros, el de la izquierda 7 gatos, su hermano mayor tenía 8 hijos si se contaban los de todas sus esposas y que en su casa eran 4 hermanos. El número de teléfono sería 253 37 84. Sus algoritmos (recetas, programas) eran enrevesados, ingeniosos, divertidos y siempre muchísimo más largos que lo que le pretendían ayudar a recordar. A veces, naturalmente, cuando tales algoritmos están íntimamente relacionados con una historia o un episodio que uno conoce muy bien, su longitud es sólo aparente y es razonable y está justificado usarlos. Sin embargo, no era éste el caso de mi amiga, que invariablemente acababa olvidando algún elemento esencial.

En el supuesto de que usted tuviera algún interés en hacerlo, ¿cómo describiría las sucesiones siguientes a un conocido que no pudiera verlas?

La primera sucesión es claramente la más sencilla, pues es una simple repetición de dos ceros y un 1. La segunda sucesión presenta alguna irregularidad —un solo 0 alternando a veces con un 1 y a veces con dos unos— mientras que la tercera sucesión es la más difícil de describir, pues no da señales de seguir ningún patrón. Nótese que el significado de los puntos suspensivos de la primera sucesión es evidente; lo es menos en la segunda, y no lo es en absoluto en la tercera. A pesar de esto, supongamos que cada una de estas sucesiones tiene un billón de bits de longitud (un bit es un 0 o un 1) y continúan «del mismo modo».

Atentos a estos ejemplos, podemos seguir al informático Gregory Chaitin y al matemático ruso A. N. Kolmogorov, y definir la complejidad de una sucesión de ceros y unos como la longitud del programa de ordenador más corto que genere dicha sucesión (esto es, que la imprima).

¿Qué quiere decir esto? Nótese que un programa que imprima la primera sucesión puede consistir simplemente en la siguiente receta: «Imprimir dos ceros, luego un 1, y repetir un tercio de billón de veces». Dicho programa es muy corto, especialmente si se compara con la longitud de la sucesión de un billón de bits que genera. La complejidad de esta primera sucesión puede ser de sólo unos 1000 bits, o la longitud que tenga el programa más corto que la produzca. Hasta cierto punto esto depende del lenguaje empleado para escribir el programa, pero independientemente de cuál sea ese lenguaje, al traducir a él «Imprimir dos ceros y luego un 1» no nos dará un programa muy largo. (Para uniformizar podemos suponer también que nuestros programas están escritos en un lenguaje de máquina muy sobrio consistente en 0 y 1, de modo que los programas que generan las sucesiones son también a su vez sucesiones de 0 y 1).

Un programa para producir la segunda sucesión podría ser una traducción de lo siguiente: «Imprimir un 0 seguido de un solo 1 o dos unos, y la pauta de los unos intermedios es 1 2 1 11112 etc.». Si esta pauta persiste, cualquier programa que imprima la sucesión habrá de ser muy largo, pues tendrá que especificar completamente la parte «etc.» de la pauta de los unos intermedios. Sin embargo, debido a la alternancia regular de ceros y unos, el programa será considerablemente más corto que la sucesión de un billón de bits que produce. Así, la complejidad de esta segunda sucesión podría ser de sólo medio billón de bits, o la longitud que tenga el programa más corto que la produzca.

Con la tercera sucesión (con mucho, el tipo más frecuente) la situación es distinta. La sucesión, lo supondremos así, es tan desordenada a lo largo de todo el billón de bits que ningún programa que la pueda generar es más corto que la sucesión misma. Todo lo que un programa puede hacer en este caso es enumerar tontamente los bits de la sucesión: «Imprimir 0, luego 1, luego 0, luego 0, luego 1, luego 0, luego 1, …». No hay modo de comprimir los puntos suspensivos ni de acortar el programa. Dicho programa sería como mínimo tan largo como la propia sucesión que ha de imprimir, con lo que la tercera sucesión tiene una complejidad de aproximadamente un billón de bits.

Una sucesión como la tercera, que precisa de un programa tan largo como ella misma para reproducirla, se llama aleatoria. Las sucesiones aleatorias no muestran ninguna pauta, regularidad ni orden, y los programas que las generan no pueden hacer sino copiarlas directamente: «Imprimir 10001011011 …». Estos programas no se pueden condensar ni abreviar. La complejidad de las sucesiones que producen es igual a la longitud de las mismas. Por contra, las sucesiones ordenadas y regulares como la primera se pueden generar con programas muy cortos y su complejidad es mucho menor que su longitud.

En ciertos aspectos, las sucesiones como la segunda son las más interesantes, pues, al igual que los seres vivos, presentan elementos de orden y elementos de azar. Su complejidad es menor que su longitud, pero no es tan pequeña como si fuera completamente ordenada ni tan grande como si fuera aleatoria. En lo que respecta a su regularidad, la primera sucesión de los ejemplos presentados se podría comparar a un diamante o a un cristal de cuarzo, mientras que la tercera sería comparable, por su aleatoriedad, a una nube de gas o a una sucesión de lanzamientos de una moneda. El análogo de la segunda podría ser algo así como una rosa (o una alcachofa, para no ser tan poéticos), que presenta a la vez orden y azar entre sus partes.

Estas comparaciones son algo más que simples metáforas. La razón de ello es que la mayoría de fenómenos se pueden describir por un código que se puede digitalizar y reducir a sucesiones de ceros y unos, tanto si es el lenguaje molecular de los aminoácidos y las moléculas de ADN como si es el idioma español de las cartas y los libros. (Véanse también las entradas sobre Música, pintura y digitalización y Test de Turing). Tanto el ADN como una novela romántica son, en sus respectivos códigos, sucesiones como la del segundo ejemplo, y presentan tanto orden y redundancia como azar y complejidad. De modo análogo, las melodías complejas se encuentran entre las simples repeticiones de golpes y el ruido informe (análogos respectivamente a las sucesiones como la primera y la tercera).

El conjunto de la ciencia podría concebirse bajo este prisma. Ray J. Solomonoff y otros autores han teorizado que las observaciones de un científico podrían codificarse en una sucesión de ceros y unos. El objeto de la ciencia sería entonces encontrar programas cortos capaces de generar dichas observaciones (derivarlas o predecirlas). Un programa semejante, según dicen, sería una teoría científica, tanto más potente cuanto más corta fuera con respecto a los fenómenos experimentales predichos. Los sucesos aleatorios no serían predictibles, excepto en el sentido muy pickwickiano de un programa que simplemente los enumerara. Tal concepción de la ciencia es bastante simplista y sólo empieza a cobrar sentido cuando se refiere a un marco científico bien definido y fijado de antemano. Sin embargo, hace pensar en la generalidad de la idea de complejidad.

El concepto de complejidad que hemos definido aquí se llama complejidad algorítmica porque se mide por la longitud del programa (algoritmo o receta) más corto necesario para generar una sucesión dada. Un concepto afín es el de complejidad computacional de una sucesión, y se define como el tiempo más corto empleado por un programa que la genere. En los problemas de aplicación práctica el tiempo es a menudo el factor más importante que determina la elección de un programa. Quizás un programa corto tarde eones en generar la sucesión que se quiere (o la predicción, según las ideas de Solomonoff sobre la ciencia), mientras que un programa más largo lo haga en menos tiempo.

La mayoría de problemas de cálculo (y recordemos que, al igual que sus soluciones, siempre se pueden codificar en sucesiones) tardan más tiempo en ser resueltos cuanto mayores son. Por tanto, el conocido problema del viajante, que pide encontrar la ruta más corta que pasa una vez por cada una de las ciudades de una cierta región y que regresa al punto de partida, es tanto más largo de resolver cuantas más ciudades tengamos que considerar.

Es importante distinguir entre los problemas matemáticos cuya complejidad computacional es una función exponencial de su tamaño y aquéllos en los cuales es una potencia del tamaño. Como ilustración de esto, en el caso del problema del viajante el tamaño está determinado por N, el número de ciudades a visitar, y no se sabe con certeza si el tiempo necesario para resolver el problema crece exponencialmente como 2^N o como una potencia N^T, donde T es un cierto exponente (generalmente pequeño). (Véase la entrada sobre Crecimiento exponencial). Un ejemplo numérico resultará aquí ilustrativo. Si tomamos N = 20 y T = 3, encontramos que 2^N = 2²⁰ = 1.048.576 mientras que N^T = 20³ = 8.000 (solamente).

Si, como se sospecha, la complejidad computacional del problema del viajante crece como 2^N, entonces el tiempo necesario para resolverlo aumenta tan rápidamente que, a efectos prácticos, el problema es irresoluble para valores muy grandes de N. (Esto no cambiaría tampoco con los procesadores en paralelo, ordenadores cuya arquitectura interna les permite realizar muchas operaciones simultáneamente en paralelo, en contraposición a los procesadores en serie de los ordenadores de hoy en día, que realizan una operación cada vez). Si la complejidad computacional crece polinómicamente como una cierta potencia de N, entonces se pueden tener soluciones completas al problema en un tiempo razonable, incluso para valores grandes de N.

La íntima alianza conceptual entre los conceptos de economía y condicionante y los de complejidad algorítmica y computacional explica la importancia creciente de éstos. La capacidad de almacenaje de cualquier ordenador es limitada y, para muchos problemas, hay que idear algoritmos más eficaces (los horarios e itinerarios de unas líneas aéreas, por ejemplo). Como ya he dicho, estos conceptos de complejidad son también importantes desde un punto de vista teórico y filosófico. Muchos teoremas, incluido el teorema de incompletitud de Gödel (véase la entrada sobre Gödel), tienen demostraciones muy naturales si se expresan en términos de complejidad. Otros enunciados, como el llamado problema de P-NP (que pregunta si los problemas cuyas soluciones propuestas se pueden comprobar rápidamente [polinómicamente] son tales que sus soluciones se pueden descubrir también rápidamente), sólo tienen sentido en el contexto de la teoría de la complejidad.