Regla de la cadena para la complejidad de Kolmogorov

Límite inferior para el tamaño del programa de software

La regla de la cadena ^{[ cita requerida ]} para la complejidad de Kolmogorov es un análogo de la regla de la cadena para la entropía de la información , que establece:

${\displaystyle H(X,Y)=H(X)+H(Y|X)}$

Es decir, la aleatoriedad combinada de dos secuencias X e Y es la suma de la aleatoriedad de X más cualquier aleatoriedad que quede en Y una vez que conocemos X. Esto se desprende inmediatamente de las definiciones de entropía condicional y conjunta , y del hecho de la teoría de la probabilidad de que la probabilidad conjunta es el producto de la probabilidad marginal y condicional :

${\displaystyle P(X,Y)=P(X)P(Y|X)}$

${\displaystyle \Rightarrow \log P(X,Y)=\log P(X)+\log P(Y|X)}$

La afirmación equivalente para la complejidad de Kolmogorov no se cumple exactamente; es verdadera sólo hasta un término logarítmico :

${\displaystyle K(x,y)=K(x)+K(y|x)+O(\log(K(x,y)))}$

(Una versión exacta, KP ( x , y ) = KP ( x ) + KP ( y | x ^∗ ) + O (1) , es válida para la complejidad de prefijo KP , donde x ^∗ es el programa más corto para x .)

Afirma que el programa más corto que imprime X e Y se obtiene concatenando un programa más corto que imprime X con un programa que imprime Y dado X , más como máximo un factor logarítmico. Los resultados implican que la información mutua algorítmica , un análogo de la información mutua para la complejidad de Kolmogorov es simétrica: ⁠ ⁠ ${\displaystyle I(x:y)=I(y:x)+O(\log K(x,y))}$ para todo x,y .

Prueba

La dirección ≤ es obvia: podemos escribir un programa para producir x e y concatenando un programa para producir x , un programa para producir y dado el acceso a x , y (de ahí el término logarítmico) la longitud de uno de los programas, de modo que sepamos dónde separar los dos programas para x e y | x (log( K ( x , y )) limita superiormente esta longitud).

Para la dirección ≥, basta mostrar que para todo k,l tal que ⁠ ⁠ ${\displaystyle k+l=K(x,y)}$ tenemos que o bien

${\displaystyle K(x|k,l)\leq k+O(1)}$

o

${\displaystyle K(y|x,k,l)\leq l+O(1)}$.

Considere la lista ( a ₁ , b ₁ ), ( a ₂ , b ₂ ), ..., ( a _e ,b _e ) de todos los pares producidos por ${\displaystyle (a,b)}$ programas de longitud exactamente [ por ${\displaystyle K(x,y)}$ lo tanto ] . ${\displaystyle K(a,b)\leq K(x,y)}$ Nótese que esta lista

• contiene el par ⁠ ⁠ ${\displaystyle (x,y)}$ ,
• se pueden enumerar dados k y l (ejecutando todos los programas de longitud ⁠ ⁠ ${\displaystyle K(x,y)}$ en paralelo),
• tiene como máximo 2 ^{K ( x , y )} elementos (porque hay como máximo 2 ⁿ programas de longitud n ).

Primero, supongamos que x aparece menos de 2 ^l veces como primer elemento. Podemos especificar y dado x,k,l enumerando ( a ₁ , b ₁ ), ( a ₂ , b ₂ ), ... y luego seleccionando ⁠ ⁠ ${\displaystyle (x,y)}$ en la sublista de pares ⁠ ⁠ ${\displaystyle (x,b)}$ . Por suposición, el índice de ⁠ ⁠ ${\displaystyle (x,y)}$ en esta sublista es menor que 2 ^l y, por lo tanto, hay un programa para y dado x,k,l de longitud ⁠ ⁠ ${\displaystyle l+O(1)}$ . Ahora, supongamos que x aparece al menos 2 ^l veces como primer elemento. Esto puede suceder para como máximo 2 ^{K ( x,y )−l} = 2 ^k cadenas diferentes. Estas cadenas se pueden enumerar dado k,l y, por lo tanto, x se puede especificar por su índice en esta enumeración. El programa correspondiente para x tiene tamaño ⁠ ⁠ ${\displaystyle k+O(1)}$ . Teorema demostrado.

Referencias

• Li, Ming; Vitányi, Paul (febrero de 1997). Una introducción a la complejidad de Kolmogorov y sus aplicaciones . Nueva York: Springer-Verlag . ISBN 0-387-94868-6.

• Kolmogorov, A. (1968). "Base lógica para la teoría de la información y la teoría de la probabilidad". IEEE Transactions on Information Theory . 14 (5). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 662–664. doi :10.1109/tit.1968.1054210. ISSN  0018-9448. S2CID  11402549.

• Zvonkin, AK; Levin, LA (1970-12-31). "La complejidad de los objetos finitos y el desarrollo de los conceptos de información y aleatoriedad por medio de la teoría de algoritmos". Russian Mathematical Surveys . 25 (6). IOP Publishing: 83–124. Bibcode :1970RuMaS..25...83Z. doi :10.1070/rm1970v025n06abeh001269. ISSN  0036-0279. S2CID  250850390.