1 Complejidad de información: la noción de complejidad teórica de la aleatoriedad

1.1 Introducción

La fundación matemática de la teoría de la probabilidad apareció entre los famosos problemas formulados por Hilbert en 1900 (antes mencionados). Von Mises realizó en 1919 un importante esfuerzo para definir la aleatoriedad de una secuencia 0-1. Su tentativa puede ser bosquejada de la siguiente forma. Se requiere que la frecuencia de los 0’s y los 1’s sea aproximadamente la misma. Esto claramente no basta, pero podríamos pedir lo mismo también para número por medio de la secuencia, o de modo más general, para todas las subsecuencias obtenidas mediante la selección de índices desde una progresión aritmética. Esta tentativa, de todas formas, no resultó ser suficientemente fructífera.

En 1931 Kolmogorov inició otra aproximación, usando teoría de medición. Su teoría fue muy exitosa desde el punto de vista de la teoría de probabilidad, y es la base del desarrollo riguroso de la teoría de la probabilidad en cualquier libro de texto hoy en día.

De cualquier forma, éste acercamiento standard no logró capturar algunos aspectos importantes. Por ejemplo, en la teoría de probabilidad basada en la teoría de medición, no podemos hablar de la aleatoriedead de una secuencia 0-1 única, sino tan sólo de la probabilidad de un conjunto de secuencias. Al mismo tiempo, por sentido común, es“obvio” que la secuencia “Cara, Cara, Cara ⋯” no puede ser el resultado del lanzamiento de una moneda. En los 60’s Kolmogorov e independientemente Chaitin revivieron la idea de Von Misses, usando herramientas de complejidad teórica. Ellos definieron la complejidad de información (contenido de información) de una secuencia; luego (a grandes rasgos), las secuencias aleatorias son aquellas cuyo contenido de información es lo más grande posible. La importancia de éstos resultados va más allá de los fundamentos de la teoría de probabilidad; contribuyen además a la clarifiación de las nociones básicas de varias áreas como la compresión de datos, la teoría de la información y la estadística.

En éste capítulo introduciremos primeramente la noción de complejidad de información. Luego discutiremos la noción de secuencia informáticamente aleatoria, y mostraremos que tales secuencias se comportan como secuencias aleatorias “usuales”: ellas obedecen la ley de grandes números. Finalmente, discutiremos el problema de codificación optimal de varias estructuras.

1.2 Complejidad de información

Fijemos un alfabeto Σ. Sea Σ_{0} = Σ\{∗} y consideremos una máquina universal de Turing T de dos cintas sobre Σ. Será conveniente identificar Σ_{0} con el conjunto {0, 1, …, m − 1} . Decimos que una palabra (programa) q sobre Σ escribe la palabra x si, escribiendo q en la segunda cinta (la cinta de programa) de T y dejando la primera cinta vacía, la máquina para en tiempo finito con la palabra x en su primera cinta (la cinta de los datos).

Permítasenos hacer notar que toda palabra se puede escribir en T. Existe particularmente una máquina de Turing S_{x} de una cinta (quizás grande, pero bastante trivial) que, cuando inicializada con la cinta vacía, escribe la palabra x en ésta y luego para. Esta máquina de Turing puede ser simulada por un programa q_{x} que, de ésta forma, imprime x.

Por complejidad de información (también llamada complejidad de Kolmogorov) de una palabra x ∈ Σ_{0}^{∗} entendemos el largo de la palabra más corta (programa) que hace a T escribir la palabra x. Denotamos la complejidad de la palabra x por K_{T} (x).

Podemos considerar también el programa que escribe x como el“código” de la palabra x y a la máquina T como el decodificador. Este tipo de código será llamado código de Kolmogorov. Por el momento, no haremos suposiciones acerca de cuanto tiempo ésta decodificación (o codificación, encontrando el programa apropiado) pueda tomar.

Nos gustaría que la complejidad sea una característica de la palabra x y que dependiera de la máquina T lo menos posible. Desafortunadamente, es posible hacer una máquina de Turing que sea obviamente “ordinaria”. Por ejemplo, que use palabra por medio de cada programa y “omita” las letras intermedias. Tal máquina puede ser universal, pero toda palabra será definida dos veces más compleja que en la máquina sin éste extran̂o comportamiento.

Mostaremos que si imponemos algunas condiciones-bastante simples-en la máquina T, entonces no continuará siendo esencial qué máquina de Turing universal sea usada para la definición de complejidad de información. A grandes rasgos, es suficiente asumir que toda entrada de una computación realizable en T puede también ser sometida como parte del programa. Para hacer ésto más exacto, asumimos que existe una palabra (digamos, DATA) para la cual lo siguiente se cumple:

(a) Toda máquina de Turing de una cinta puede ser simulada por un programa que no contenga la palabra DATA como subpalabra;

(b) Si la máquina es inicializada de tal forma que su programa contenga una palabra de la forma xDATAy, donde la palabra x no contiene a la subpalabra DATA, entonces la máquina para, si y sólo si ésta para cuando se inicializa con y escrita en la cinta de los datos y x en la cinta de programa, y de hecho con la misma salida en la cinta de los datos.

Es fácil ver que toda máquina de Turing universal puede ser modificada para satisfacer (a) y (b). En lo que sigue, siempre asumiremos que nuestra máquina de Turing universal tiene éstas propiedades.

(7.1) Lema Existe una constante c_{T} (que sólo depende de T) tal que K_{T} (x) ≤ |x| + c_{T} .

Demostración T es universal, por lo tanto la máquina de Turing de una cinta (trivial) que no hace nada (para inmediatamente) puede ser simulada en ella por un programa p_{0} (que no contenga la palabra DATA). Pero entonces, para cada palabra x ∈ Σ_{0}^{∗}, el programa p_{0}DATAx escribirá la palabra x y parará. De éste modo la constante c_{T} = |p_{0}| + 4 satisface la condición.

En lo que sigue asumimos, para ser específicos, que c_{T} ≤ 100 .

(7.2) Observación Tuvimos que ser cuidadosos ya que no queríamos restringir los símbolos que pudieran ocurrir en x. En BASIC, por ejemplo, la instrucción PRINT “x” no es adecuada para escribir palabras x que contengan el símbolo ”. Nosotros estamos interesados en saber cuán concisamente la palabra x puede ser codificada en el alfabeto dado, y no permitimos por tanto la extensión del alfabeto.

Probaremos ahora el teorema básico que muestra que la complejidad (bajo las condiciones (a) y (b) no depende demasiado de la máquina dada.

(7.3) Teorema de Invarianza Sean T y S máquinas de Turing universales que satisfacen condiciones (a) y (b). Entonces existe una constante c_{T S} tal que para cada palabra x se tiene que |K_{T} (x) − K_{S}(x)| ≤ c_{T S}.

Demostración Podemos simular la máquina S de Turing de dos cintas por una máquina de Turing S_{0} de una cinta de tal forma que si en S, un programa q escribe una palabra x, entonces escribiendo q en la cinta de S_{0}, para en pasos finitos, con x escrito en su cinta. Más aún, podemos simular el accionar de la máquina de Turing S_{0} en T mediante un programa p_{S_{0}} que no contenga a DATA como subpalabra.

Sea x una palabra arbitraria de Σ_{0}^{∗} y q_{x} el programa más corto que escriba x en S. Considere el programa p_{S_{0}}DATAq_{x} en T: éste obviamente escribe x y tiene largo de sólo |q_{x}| + |p_{S_{0}}| + 4. La desigualdad en la otra dirección se obtiene de manera similar.

En la base de éste lema, no restringiremos generalidad si consideramos T fijo y no indicamos el índice de T.

Desafortunadamente, el siguiente teorema muetsra que el código optimal no puede ser encontrado mediante un algoritmo.

(7.4) Teorema La función K(x) no es recursiva.

Demostración La esencia de la demostración es una paradoja de la lógica clásica, la llamada “paradoja de Richard ”. (Esta puede ser formulada simplemente como sigue: sea n el número más pequeño que no puede ser definido con menos de 100 símbolos ¡Pero entonces hemos definido n con menos de 100 símbolos!)

Asumamamos, por medio de contradicción, que K_{x} es computable. Sea c un número natural elegido apropiadamente. Arreglemos los elementos de Σ_{0}^{∗} en orden creciente, y permitamos que x_{k} denote la k-ésima palabra de acuerdo a éste orden. Sea x_{0} la primera palabra tal que K(x_{0}) ≥ c . Asumiendo que nuestro lenguaje puede ser programado en el lenguaje PASCAL consideremos el siguiente simple programa.

var k: integer; function x(k : integer): integer . . . function Kolm(k: integer): integer; . . . begin

k:=0;

while Kolm(k) < c do k:=k+1; print(x(k));

end.

(Las partes punteadas representan subrutinas que computen las funciones dadas. La primera es fácil y podría ser incluída explícitamente. La segunda es hipotética, basada en el supuesto de que K(x) es computable.)

Este programa obviamente escribe x_{0}. Cuando determinemos su largo debemos tener en consideración las subrutinas para la computación de las funciones x(k) y Kolm(k) = K(x_{k}) (donde x(k) es la k-ésima palabra según el orden arriba propuesto); pero ésta es una constante (independiente de c). De éste modo, aún considerados juntos, el número de todos éstos símbolos es sólo log c + O(1) . Si tomamos c lo suficientemente grande éste programa consiste en menos de c símbolos y escribe x, lo que es una contradicción.

Como aplicación simple del teorema, ontenemos una nueva prueba de la indecibilidad del problema de parada. Con éste fin hagámonos la siguiente pregunta: ¿Por qué no es posible computar K_{x} de la siguiente forma? Tome todas las palabras y en orden creciente y compruebe si T escribe x cuando se inicializa con y en su cinta de programa. Retorne la primera y para la cual ésto suceda; su largo es K(x).

Sabemos que algo debe estar incorrecto aquí, ya que K(x) no es computable. El único pronlema con éste algoritmo es que T podría no parar con algún y. Si el problema de parada fuera decidible, podríamos “deshacernos” a medida que avanzamos de de los programas en los que T trabajara para siempre, y no intentarlos siquiera. De éste modo podríamos computar K(x).

Por lo tanto, el problema de parada no es decidible.

En contraste con el teorema 7.4, nosotros mostraremos que K(x) puede ser bien aproximado en el promedio.

Para ésto primero debemos hacer preciso a qué nos referimos con “en el promedio”. Asuma que las palabras de entrada vienen de alguna distribución de probabilidad; o de otra forma, que toda palabra x ∈ Σ_{0}^{∗} tiene una probabilidad p(x). Por tanto

p(x) ≥ 0,  ∑_{x∈Σ_{0}^{∗}} p(x) = 1.

.

Asumimos que p(x) es computable, i.e. cada p(x) es un número racional cuyo numerador y denominador son computables desde x. Un simple ejemplo de distribución de probabilidad computable es p(x_{k}) = 2^{−k}, donde x_{k} es la k ésima palabra en orden de taman̂o, o p(x) = (m + 1)^{−|x|−1}, donde m es el taman̂o del alfabeto.

(7.5) Observación Existe una noción más general de distribución de probabilidad computable que no restringe probabilidades a números racionales; por ejemplo {e^{−1}, 1 − e^{−1}} podría ser considerado una distribución de probabilidad computable. Sin ir a los detalles hacemos la observación que nuestros teoremas se conservan para ésta clase más general.

(7.6) Teorema Para toda distribución de probabilidad computable hay un algoritmo computando un código de Kolmogorov f(x) para toda palabra x tal que la esperanza de |f(x)| − K(x) es finito.

Demostración Para la simplicidad de la prentación, asuma que p(x) > 0 para toda palabra x. Sea x_{1}, x_{2}, … un orden de las palabras de Σ_{0}^{∗} para el cual p(x_{1}) ≥ p(x_{2}) ≥ …, y las palabras con igual probabilidad están, digamos, en orden creciente (puesto que cada palabra tiene probabilidad positiva, para todo x existe sólo un número finito de palabras con probabilidad al menos p(x), y por ello ésta es efectivamente una única secuencia).

(7.7) Lema (a) Dada una palabra x, el índice i para el cual x = x_{i} es computable.

(b) Dado un número natural i, la palabra x_{i} es computable. Demostración Sea y_{1}, y_{2}, … todas las palabras ordenadas en orden

creciente. Dada una palabra x, es fácil encontrar el índice j para el cual x = y_{j}. Luego, encuentre el primer k ≥ j para el cual

p(y_{1}) + ⋯ + p(y_{k}) > 1 − p(y_{j}).

Puesto que el lado izquierdo converge a 1, mientras el lado derecho es menor que 1, ésto ocurrirá tarde o temprano.

Claramente cada una de las palabras sobrantes y_{k+1}, y_{k+2}, … tiene probabilidad menor que p(y_{j}), y por lo tanto para determinar el índice de x = y_{j} basta ordenar el conjunto finito {y_{1}, …, y_{k}} de acuerdo a p decreciente, y a encontrar el índice de y_{j} entre ellos.

(b) Dado un índice i, podemos computar los índices de y_{1}, y_{2}, … usando (a) y esperando hasta que i aparezca.

Retornando a la demostración del teorema, el programa del algoritmo en el lema anterior, junto con el número i, proporciona un código de Kolmogorov f(x_{i}) para la palabra x_{i}. Demostraremos que éste código satisface los requerimientos del teorema. Obviamente, |f(x)| ≥ K(x). Además, el valor esperado de |f(x)| − K(x) es

∑_{i=1}^{∞} p(x_{i})(|f(x_{i})| − K(x_{i})).

Queremos demostrar que el valor de ésta sumatoria es finito. Ya que sus términos son no-negativos, basta demostrar que sus sumas parciales permanecen acotadas, i.e., que

∑_{i=1}^{N} p(x_{i})(|f(x_{i})| − K(x_{i})) < C

para algún C independiente de N. Para terminar, escribimos

∑_{i=1}^{N} p(x_{i})(|f(x_{i})| − K(x_{i})) (7.9)

= ∑_{i=1}^{N} p(x_{i})(|f(x_{i})| − log_{m} i) + ∑_{i=1}^{N} p(x_{i})(log_{m} i − K(x_{i})). (7.10)

Ambas sumas permanecen acotadas. De hecho, la diferencia |f(x_{i})| − log_{m} i es sólo el largo del programa computando x_{i} sin el largo del parámetro i, y por lo tanto es una constante absoluta C. De aquí que la primera suma en (7.9) es a lo más C.

Para estimar el segundo término en (7.9), usamos el siguiente simple pero útil principio. Sea a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{m} una secuencia decreciente y b_{1} … b_{m} una secuencia arbitraria de números reales. Sea b_{1}^{∗} ≥ ⋯ ≥ b_{m}^{∗} la secuencia b ordenada decrecientemente, y b_{1}^{∗∗} ≤ ⋯ ≤ b_{m}^{∗∗} la secuencia b ordenada crecientemente. Entonces

∑_{i} a_{i}b_{i}^{∗∗} ≤ ∑_{i} a_{i}b_{i} ≤ ∑_{i} a_{i}b_{i}^{∗}.

Sea (z_{1}, z_{2}, …) un orden de las palabras tal que K(z_{1}) ≤ K(z_{2}) ≤ … (no podemos computar éste orden, pero no tenemos que computarlo). Entonces por el principio de arriba,

∑_{i=1}^{N} p(x_{i})K(x_{i}) ≥ ∑_{i=1}^{N} p(x_{i})K(z_{i}).

El número de palabras x con K(x) = k es a lo más m^{k}, y por ello el número de palabras x con K(x) ≤ k es a lo más 1 + m + ⋯ + m^{k} < m^{k+1}. Esto es lo mismo que decir que

i ≤ m^{K(z_{i})+1},

y por lo tanto

K(z_{i}) ≥ log_{m} i − 1.

De éste modo

∑_{i=1}^{N} p(x_{i})(log_{m}i − K(x_{i})) ≤ ∑_{i=1}^{N} p(x_{i})(log_{m} i − K(z_{i})) ≤ ∑_{i=1}^{N} p(x_{i}) = 1.

Esto prueba el teorema.

1.3 La noción de secuencia aleatoria

En ésta sección asumimos que Σ_{0} = {0, 1}, i.e. consideraremos sólo la complejidad de secuencias {0,1}. Informalmente hablando, queremos considerar una secuencia aleatoria si no hay “regularidad” en ella. En ésto, queremos ser tan generales como se pueda y considerar cualquier tipo de regularidad que permitiera una codificación más económica de la secuencia (tal que la complejidad de la secuencia sea pequen̂a).

(7.1) Observación Note que ésta no es la única idea posible de regularidad. Uno podría considerar una secuencia 0 − 1 regular si el número de 0’s en ella es el mismo que el número de 1’s. Esta clase de regularidad es compatible con (en efecto, implicada por) aleatoriedad: deberíamos considerar realmente sólo regularidades que son compartidas únicamente por una pequen̂a minoría de las secuencias.

Estimemos primero la complejidad se secuencias 0 − 1 promedio.

(7.2) Lema El número de secuencias 0−1 de largo n con K(n) ≤ n−k es menor que 2^{n−k+1}.

Demostración El número de codificaciones de largo a lo más n − k es a lo más 1 + 2 + ⋯ + 2^{n−k} < 2^{n−k+1}, por lo tanto sólo menos de 2^{n−k+1} palabras x pueden tener tal código.

(7.3) Corolario La complejidad del 99% de las secuencias 0 − 1 de n-dígitos es mayor que n − 7. Si elegimos una secuencia 0 − 1 de largo n al azar, entonces |K(x) − n| ≤ 100 con probabilidad 1 − 2^{100}.

Otro corolario de éste simple lema es que muestra, en cierto sentido, un “contraejemplo” a la Tesis de Church, como notamos en la introducción a la sección de computación aleatorizada. Considere el siguiente problema: Para un n dado, construya una secuencia 0 − 1 de largo n cuya complejidad de Kolmogorov sea mayor que n/2. De acuerdo al ejercicio mencionado después del Teorema (7.4), éste problema es algorítmicamente indecidible. Por otro lado, el lema anterior muestra que con probabilidad grande, una secuencia elegida aleatoriamente es apropiada.

De acuerdo al Teorema (7.4), es algorítmicamente imposible encontrar el mejor código. Hay, sin embargo, algunas propiedades fácilmente reconocibles indicando de una palabra que ella es codificable más eficientemente que su largo. El siguiente lema muestra tal propiedad:

(7.4)Lema Si el número de 1’s en una secuencia x 0 − 1 de largo n es k entonces

K(x) ≤ log_{2} \binom{n}{k} + log_{2} n + log_{2} k + O(1).

Sea k = pn (0 < p < 1), entonces ésto puede ser estimado como

K(x) ≤ (−p log p − (1 − p) log(1 − p))n + O(log n).

En particular, si k > (1/2 + ε)n o k < (1/2 − ε)n entonces

K(x) ≤ cn + O(log n)

donde c = −(1/2 + ε) log(1/2 + ε) − (1/2 − ε) log(1/2 − ε) es una constante positiva más pequen̂a que 1 y dependiente sólo de ε.

Demostración x puede ser descrito como la “léxicograficamente t-ési-ma secuencia entre todas las secuencias de largo n conteniendo exactamente k′s 1’s”. Ya que el número de secuencias de largo n que contienen k 1’s es \binom{n}{k},

la descripción de los números t, n y k necesita sólo log_{2} \binom{n}{k}+2 log_{2} n+2 log_{2} k bits. (Aquí el factor 2 se debe a la necesidad de separar las tres piezas de información entre si; dejamos al lector que encuentre el truco). El programa que elige la secuencia apropiada necesita sólo un número constante de bits.

La estimación del coeficiente binomial es hecha por un método familiar de la teoría de la probabilidad.

En base a lo expresado, uno puede considerar ya sea |x|−K(x) o |x|/K(x) como una medida de la aleatoriedad (o mejor, de la no aleatoriedad) de la palabra x. Mientras más grandes son éstos números, más pequen̂o es K(x) relativo a |x|, lo que significa que x tiene mayor “regularidad” y por lo tanto es menos aleatorio.

En el caso de las secuencias infinitas, una diferencia más exacta puede ser hecha: podemos definir si una secuencia dada es aleatoria. Varias definiciones son posibles: introduciremos aquí la versión más simple. Sea x una secuencia infinita 0 − 1, y permita que x_{n} denote su segmento inicial formado por los primeros n elementos. Llamamos a la secuencia x informáticamente aleatoria si K(x_{n}) → 1 cuando n → ∞.

Puede ser demostrado que toda secuencia informática y débilmente aleatoria satisface la ley de grandes números. Consideramos aquí sólo el más simple de tales resultados. Si a_{n} denota el número de 1’s en la palabra x_{n}, entonces el lema previo inmediatamente implica el siguiente teorema:

(7.5) Teorema Si x es informáticamente aleatorio, entonces a_{n}/n → 1/2 (n → ∞).

El problema aparece si la definición de secuencia algorítmicamente aleatoria no es demasiado estricta, si es que existen secuencias infinitas algorítmica mente aleatorias. Mostraremos que no sólo existen tales secuencias, sino que casi todas las secuencias tienen ésta propiedad:

(7.6) Teorema Sean los elementos de una secuencia 0 − 1 infinita x variables aleatorias independientes con probabilidad 1/2. Entonces x es algorítmicamente aleatoria con probabilidad 1.

Demostración Para un ϵ > 0 fijo, sea S el conjunto de todas aquellas secuencias infinitas y, para las cuales K(y) < (1−ϵ)|y|, y A_{n} denota el evento x_{n} ∈ S. Entonces por lema 7.2,

P rob(A_{n}) ≤ ∑_{y∈S} 2^{−n} < 2^{(1−ϵ)n} + 12^{−n} = 2^{1−ϵn},

y por ésto la suma ∑_{k=1}^{∞} P rob(A_{n}) es convergente. Pero entonces, el Lema de Borel-Cantelli de la teoría de probabilidad implica que con probabilidad 1, sólo un conjunto finito de los eventos A_{k} ocurre. Pero ésto sólo significa que K(x_{n})/n → ∞.

1.4 Complejidad de Kolmogorov y compresión de datos

Sea L ⊂ Σ_{0}^{∗} un lenguaje recursivo y suponga que queremos encontrar un programa corto, “código” sólo para las palabras en L. Para cada palabra x en L, estamos de éste modo buscando un programa f(x) ∈ {0, 1}^{∗} que lo escriba. Llamamos a la función f : L → Σ^{∗} un código de Kolmogorov de L. La concisión del código es la función

η(n) = max{|f(x)| : x ∈ L, |x| ≤ n}.

Podemos fácilmente obtener una cota inferior para la concisión de cualquier código de Kolmogorov de algún lenguaje. Si L_{n} denota el conjunto de palabras de de largo a lo más n, entonces obviamente,

η(n) ≥ log_{2} |L_{n}|.

Llamamos a ésta estimación la cota inferior de información teórica.

Esta cota inferior es exacta. Podemos codificar toda palabra x en L simplemente diciendo su número serial en orden creciente. Si la palabra x de largo n es el t-ésimo elemento, entonces éste requiere log_{2} t ≤ log_{2} |L_{n}| bits, más un número constante de bits adicionales (el programa que toma los elementos de Σ^{∗} en orden léxicografico, comprueba su pertenencia a L y escribe el t-ésimo de ellos).

Llegamos a problemas más interesantes si estipulamos que el código desde la palabra, y conversamente, la palabra desde el código debieran ser polinomialmente computables. En otras palabras, estamos buscando un lenguaje L’y dos funciones polinomialmente computables:

f : L → L′, g : L′ → L

con g ∘ f = id para el cual, para todo x en L el código |f(x)| es “corto” comparado con |x|. Tal par de funciones es llamada un código de tiempo polinomial. (En vez de límites de tiempo polinomial podríamos, por supuesto, considerar otras restricciones de complejidad.)

Presentaremos algunos ejemplos de cuando un código de tiempo polinomial se aproxima al límite teórico de información.

(7.1) Ejemplo En la demostración del Lema 7.4, para la codificación de las secuencias 0 − 1 de largo n con exaxtamente m 1’s, usamos la simple codificación en la cual el código de una secuencia es el número que le da su lugar en el ordenamiento léxicografico. Mostraremos que ésta codificación es polinomial.

Permítasenos ver cada secuencia 0 − 1 como el código obvio de un subconjunto del conjunto de n elementos {n−1, n−2, …, 0}. Cada uno de tales conjuntos puede ser escrito como {a_{1}, … a_{m}}, donde a_{1} > a_{2} > ⋯ > a_{m}.

Entonces el conjunto {b_{1}, …, b_{m}} precede al conjunto {a_{1}, …, a_{m}} léxicografica mente si y sólo si existe un i tal que b_{i} < a_{i} mientras a_{j} = b_{j} sea válido para todo j < i. Sea {a_{1}, …, a_{m}} el léxicograficamente t-ésimo conjunto. Entonces el número de subconjuntos {b_{1}, …, b_{n}} con ésta propiedad es exactamente \binom{a_{i}}{m−i+1}. Sumando para todos los i encontramos que

t = 1 + \binom{a_{1}}{m} + \binom{a_{2}}{m − 1} + ⋯ + \binom{a_{m}}{1}. (7.2)

Dado a_{1}, …, a_{m}, el valor de t es fácilmente computable en tiempo polinomial en el largo de n. Recíprocamente, si t < \binom{n}{m} nos es dado, es fćil escribirlo en la forma de arriba: primero encontramos, usando búsqueda binaria, el mayor número natural a_{1} con \binom{a_{1}}{m} ≤ t − 1, después el mayor número a_{2} con

\binom{a_{2}}{m−1} ≤ t − 1 − \binom{a_{1}}{m}, etc. Hacemos ésto durante m pasos. Los números obtenidos de ésta manera satisfacen a_{1} > a_{2} > …; en efecto, de acuerdo a la definición de a_{1} tenemos que \binom{a_{1}+1}{m} = \binom{a_{1}}{m} + \binom{a_{1}}{m−1} > t − 1 y por lo tanto

\binom{a_{1}}{m−1} > t − 1 − \binom{a_{1}}{m}, lo que implica que a_{1} > a_{2}. Similarmente se sigue que a_{2} > a_{3} > … > a_{m} ≥ 0, y que no hay “resto” luego de m pasos, i.e. que (7.2) se cumple. Por lo tanto, puede ser determinado en tiempo polinomial qué subconjunto es léxicograficamente el t-ésimo.

(7.3) Ejemplo Considere árboles dados por su matriz de adyacencia (cualquier otra representación “razonable” podría servir también). En tales representaciones, los vértices del árbol tienen un orden dado, lo cual podemos expresar también diciendo que están numerados desde 0 hasta (n − 1). Consideramos que dos árboles son iguales si, cuando sea que dos nodos i, j están conectados en el primer árbol también lo están en el segundo y vice versa (de tal forma que si renumeramos los nodos del árbol obtenemos un árbol diferente). Tales árboles son llamados árboles rotulados. Permítasenos primero ver qué nos entrega la cota inferior teórica de información, i.e., cuántos árboles hay. El siguiente clásico resultado, llamado Teorema de Cayley se aplica aquí:

(7.4) Teorema El número de árboles rotulados de n-nodos es n^{n−2}.

Por consiguiente, por la cota inferior teórica de información, para cualquier codificación un árbol de n-nodos necesita un código con largo al menos ⌈log(n^{n−2})⌉ = ⌈(n − 2) log n⌉. Pero, ¿puede ésta cota inferior ser lograda por algún código computable de tiempo polinomial?.

(a) Codificar árboles por su matriz de adjacencia toma n^{2} bits.

(b) Nos encontraremos en una mejor situación si especificamos cada árbol enumerando sus ejes. Entonces debemos dar un “nombre” a cada vértice; ya que hay n vértices podemos dar a cada uno una secuencia 0 − 1 de largo ⌈log n⌉ como nombre. Especificamos cada eje por sus dos nodos terminales. De ésta manera la enumeración de los ejes toma 2(n − 1) log_{2} n bits.

(c) Podemos salvar un factor de 2 en (b) si distinguimos una raíz en el árbol, digamos el nodo 0, y especificamos el árbol por la secuencia (α(1), …, α(n − 1)), en la cual α(i) es el primer nodo interior en el camino desde el nodo i hasta la raíz (el “padre” de i). Esto es (n − 1)⌈log n⌉ bits, lo que es ya casi óptimo.

(d) Existe, de todas formas, un procedimiento, el llamado código Prüfer, que realiza una biyección entre los árboles rotulados de n-nodos y las secuencias de largo n − 2 de los números 0, …, n − 1 (por lo cual también prueba el Teorema de Cayley). Cada una de tales secuencias puede ser considerada la expresión de un número natural en el sistema numérico base n; de ésta forma conferimos un “número serial” entre 0 y n^{n−2} a los árboles rotulados de n-nodos. Expresando éstos números seriales en el sistema numérico base 2, obtenemos una codificación en la cual el código de cada número tiene largo a lo más ⌈(n − 2) log n⌉.

El código Prüfer puede ser considerado un refinamiento del procedimiento en (c). La idea es que ordenemos los ejes [i, α(i)] no por la magnitud de i, sino de una forma levemente diferente. Definamos la permutación de (i_{1}, …, i_{n}) como sigue: sea i_{1} el nodo terminal (hoja) más pequen̂o del árbol; si i_{1} … i_{k} están ya definidos, entonces i_{k+1} es el nodo terminal más pequen̂o del grafo que queda depués de de borrar los nodos i_{1}, …, i_{k} (no consideramos la raíz 0 como un nodo terminal). Sea i_{n} = 0. Con los i_{k}’s de éste modo definidos consideremos la secuencia (α(i_{1}), …, α(i_{n−1})). El último elemento de ésta es 0 (el “padre” del nodo i_{n−1} puede ser sólo i_{n}), y por lo tanto no es interesante. Llamamos a la secuencia restante (α(i_{1}), …, α(i_{n−2})) el código de Prüfer del árbol.

(7.5) Declaración El código de Prüfer de un árbol determina el árbol.

Para ésto es suficiente ver que el código Prüfer determina la secuencia i_{1}, …, i_{n}; entonces conocemos todos los ejes del árbol (los pares [i, α(i)]).

El nodo i_{1} es el nodo terminal más pequen̂o del árbol; por ésto, para determinar i_{1} es suficiente obtener los nodos terminales desde el código Prüfer.

Pero ésto es obvio: los nodos terminales son exactamente aquellos que no son los “padres” de otros nodos, i.e. los que no ocurren entre los números α(i_{1}), …, α(i_{n−1}), 0. El nodo i_{1} está por tanto únicamente determinado.

Asuma que sabemos ya que el código Prüfer determina únicamente i_{1}, …, i_{k−1}. Se sigue similarmente a lo de arriba que i_{k} es el número más pequen̂o que no ocurre ni entre i_{1}, …, i_{k−1} ni entre α(i_{k}), …, α(i_{n−1}). De ésta forma, i_{k} está también únicamente determinado.

(7.6) Declaración Toda secuencia (b_{1}, …, b_{n−2}), donde 1 ≤ b_{i} ≤ n, ocurre como código Prüfer de algún árbol.

Usando la idea de la prueba de arriba, sea b_{n−1} = 0 y definamos la permutación i_{1}, …, i_{n} mediante la recursión de que i_{k} es el número más pequen̂o que no ocurre ni en i_{1}, …, i_{k−1} ni en b_{k}, …, b_{n−1}, donde 1 ≤ k ≤ n − 1: y sea i_{n} = 0. Conecte i_{k} con b_{k} para todo 1 ≤ k ≤ n − 1 y sea γ(i_{k}) = b_{k}. De ésta manera obtenemos un grafo G con n−1 ejes en los nodos 1, …, n. Este grafo es conexo, ya que para cada i el nodo γ(i) viene después que i en la secuencia i_{1}, …, i_{n} y por lo tanto la secuencia i, γ(i), γ(γ(i)), … es un camino conectando i al nodo 0. Pero entonces G es un grago conexo con n − 1 ejes, por lo que es un árbol. Que la secuencia (b_{1}, …, b_{n−2}) es el código Prüfer de G es obvio a partir de la construcción.

(7.7) Observación Una correspondencia exacta como el código Prüfer tiene otras ventajas junto con la de codificación de Kolmogorov optimal. Suponga que nuestra tarea es escribir un programa para una máquina de Turing aleatoria que entregue un árbol rotulado aleatorio de taman̂o n de tal forma que todos los árboles ocurren con la misma probabilidad. El código Prüfer nos da un algoritmo eficiente para ésto. Tenemos que sólo generar aleatoriamente una secuencia b_{1}, …, b_{n−2}, lo que es fácil, y luego decodificar de ésta el árbol por el algoritmo anterior.

(7.8) Ejemplo Considere ahora los árboles no rotulados. Estos pueden ser definidos como las clases de equivalencia de los árboles rotulados donde dos árboles son considerados equivalentes si son isomórficos, i.e. por una re-rotulación adecuada se convierten en el mismo árbol rotulado. Asumimos que representamos cada clase de equivalencia por uno de sus elementos, i.e. por un árbol rotulado (no es interesante ahora, por cuál). Ya que cada árbol rotulado puede ser rotulado a lo más de n! maneras (¡sus rotulaciones no son necesariamente todas diferentes como árboles rotulados!) el número de árboles no rotulados es al menos n^{n−2}/n! ≤ 2^{n−2}. (De acuerdo a un difícil resultado de George Pólya, el número de árboles no rotulados de n nodos es asintóticamente c_{1}c_{2}^{n}n^{3/2}, donde c_{1} y c_{2} son constantes definidas de cierta manera complicada). La cota inferior de información teórica es, por lo tanto, al menos n − 2.

Por otra parte, podemos usar el siguiente procedimiento de codificación. Considere un árbol F de n-nodos. Recorrra F mediante la siguiente regla de “búsqueda en profundidad”: sea x_{0} el nodo rotulado con 0 y defina los nodos x_{1}, x_{2}, … como sigue: si x_{i} tiene un vecino que no ocurre aún en la secuencia, entonces permita que x_{i+1} sea el más pequen̂o entre éstos. Si no tiene y x_{i} = x_{0}, entonces permita que x_{i+1} sea el vecino de x_{i} en el camino que va de x_{i} a x_{0}. Finalmente, si x_{i} = x_{0} y todo vecino de x_{0} ya ocurrió en la secuencia, entonces pare.

Es fácil ver que para la secuencia de éste modo definida, todo eje ocurre entre los pares [x_{i}, x_{i+1}], más aún, ocurre una vez en ambas direcciones. Se sigue que el largo de la secuencia es exactamente 2n − 1. Ahora, sea ϵ_{i} = 1 si x_{i+1} está más lejos de la raíz que x_{i} y ϵ_{i} = 0 de otra forma. Es fácil entender que la secuencia ϵ_{0}ϵ_{1} ⋯ ϵ_{2n−3} determina el árbol únicamente; pasando a través de la secuencia, podemos dibujar el grafo y construir la secuencia x_{1}, …, x_{i} de nodos paso a paso. En el paso i+1, si ϵ_{i} = 1 entonces tomamos un nuevo nodo (que será x_{i+1}) y lo conectamos con x_{i}; si ϵ_{i} = 0 entonces permita que x_{i+1} sea el vecino de x_{i} en la “dirección” de x_{0}.

(7.9) Observaciónes

1. Con ésta codificación, el código asignado a un árbol depende de la rotulación pero no determina el árbol únicamente (sólo determina el árbol no rotulado únicamente).

2. La codificación no es biyectiva: no toda secuencia 0-1 será el código de un árbol no rotulado. Notamos que:

(a) Hay tantos 1’s como 0’s en cada árbol;

(b) En todo segmento inicial de un código hay al menos tantos 1’s como 0’s.

(la difrencia entre el número de 1’s y el número de 0’s entre los primeros i números entrega la distancia al nodo x_{i} desde el nodo 0). Es fácil darse cuenta que para cada secuencia 0-1 que tiene las propiedades (a) y (b), existe un árbol rotulado de la que es código. No es seguro, de todas formas, que éste árbol, como árbol no rotulado, sea dado con sólo ésta rotulación (ésto depende de cuáles árboles no rotulados están representados por cuál de sus rotulaciones). Por lo tanto el código no usa ni siquiera todas las palabras con propiedades (a) - (b).

3. El número de secuencia 0-1 que tienen propiedades (a) - (b) es, de acuerdo a un conocido teorema combinatorial, \frac{1}{n} \binom{2n−2}{n−1} (el llamado número catalan). Podemso formular una noción de árbol para la cual las secuencias con propiedades (a) - (b) correspondan exactamente: éstos son los árboles planares arraigados, que se dibujan sin intersección en el plano de tal forma que su vértice distinguido - su raíz - esté en el extremo izquierdo de la página. Este dibujo define un ordenamiento entre los “hijos” (vecinos más lejanos de la raíz) de “arriba a abajo”; el dibujo está caracterizado por éstos ordenamientos. El código arriba descrito puede también ser hecho en árboles planares arraigados y crea una biyección entre ellos y las secuencias con propiedades (a) - (b).