Complejidad de Kolmogorov

En informática teórica y matemáticas , más precisamente en teoría de la información , la complejidad de Kolmogorov , o complejidad aleatoria , o complejidad algorítmica de un objeto (número, imagen digital , cadena ) es el tamaño del algoritmo más pequeño (en un determinado lenguaje de programación fijo). que genera este objeto. Lleva el nombre del matemático Andrei Kolmogorov , quien publicó sobre el tema ya en 1963. A veces también se le llama complejidad Kolmogorov-Solomonoff . Esta cantidad puede verse como una evaluación de una forma de complejidad del objeto.

Ejemplos de

Primer ejemplo: cadenas de texto

Considere dos textos, cada uno compuesto por una cadena de 32 caracteres:

abababababababababababababababab y 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

El primero de estos dos textos puede ser generado por el abalgoritmo " 16 tiempos", es decir por un algoritmo de 10 caracteres, mientras que el segundo no parece tener ningún pequeño algoritmo que lo genere aparte del algoritmo que consiste en escribir este cadena de caracteres, es decir, un algoritmo de 32 caracteres. Por tanto, el primer texto parece tener una complejidad de Kolmogorov menor que la del segundo.

Segundo ejemplo: una imagen

La figura de la derecha muestra una imagen de mapa de bits que muestra el conjunto de Mandelbrot . Esta imagen de 24 bits pesa 1,61 mebabytes. Por otro lado, un pequeño algoritmo puede reproducir esta imagen a partir de la definición matemática del conjunto de Mandelbrot y las coordenadas de las esquinas de la imagen. Por tanto, la complejidad de Kolmogorov de la imagen de mapa de bits (sin comprimir) es inferior a 1,61 mebibytes en un modelo computacional razonable.

Definición

Considere una máquina de computadora $M$ capaz de ejecutar programas. Se dice que esta máquina es universal cuando puede emular cualquier otra computadora. La máquina universal de Turing es un ejemplo.

Denotamos $P M$ todos los programas escritos para la máquina $M$ . Para un programa $p \in P M$ , denotamos por $l ( p )$ de su longitud en número de instrucciones para la máquina $M$ y $s ( p )$ su salida. La complejidad de Kolmogorov $K M ( x )$ , o complejidad algorítmica, de una secuencia finita $x$ de caracteres para una máquina $M$ se define por:

K_M (x) = \ min_ {p \ in P_M} \ {l (p), s (p) = x \}

Por tanto, es la longitud del programa más pequeño escrito para la máquina $M lo$ que genera la secuencia $x$ . Una secuencia constante tiene baja complejidad porque los programas que la generan pueden ser muy cortos.

Queda por ver hasta qué punto la función $K M ( x )$ depende de la máquina $M$ , porque es muy posible imaginar una máquina que tenga instrucciones simples para generar ciertas secuencias complejas. La respuesta es la siguiente: existe una máquina universal $U$ (a menudo llamada aditivamente óptima) tal que para cualquier máquina $M$ existe una constante $c M que$ verifica para cualquier secuencia $x$ la desigualdad:

K_U (x) \ leq K_M (x) + c_M

Intuitivamente, $c M$ es la longitud de una cáscara (o emulador ), escrito para la máquina de $U$ , el lenguaje utilizado por la máquina $M$ . Hablamos entonces de la universalidad de la complejidad de Kolmogorov, en el sentido de que no depende, salvo por una constante aditiva, de la máquina considerada.

Entonces, una secuencia puede considerarse tanto más "aleatoria" cuanto mayor sea su complejidad en comparación con su tamaño. Desde este punto de vista, los decimales de los números $π$ , $e$ o √ 2 no son realmente aleatorios ya que existen algoritmos muy sencillos para calcularlos.

Una dificultad adicional radica en el hecho de que la complejidad de Kolmogorov no es decidible : podemos dar un algoritmo que produzca el objeto deseado, lo que demuestra que la complejidad de este objeto es como máximo del tamaño de este algoritmo. Pero no puede escribir un programa que proporcione la complejidad de Kolmogorov a cualquier objeto que desee darle como entrada.

Sin embargo, el concepto, manejado con cuidado, resulta ser la fuente de muchos resultados teóricos.

Por ejemplo, se llama número incompresible en el sentido de Kolmogorov a un real cuyo desarrollo p-ádico (binario para mayor comodidad) es comparable al tamaño del algoritmo que permite calcularlo. En este sentido, todos los racionales y algunos irracionales son comprimibles, en particular los números trascendentes como $π$ , $e$ o 0.12345678910111213… cuya expansión binaria es infinita pero la secuencia de decimales es perfectamente computable. Por otro lado, el llamado número Chaitin $Ω$ no lo es: este número mide la probabilidad de que una máquina, alimentada por un programa compuesto por bits aleatorios, se detenga. La topología de los números incompresibles es interesante: intuitivamente concebimos que este conjunto es denso en , pero es imposible exhibir algorítmicamente un real incompresible, ya que eso equivaldría a darle un método de cálculo eficiente. Además, podemos demostrar que todos los números incompresibles son normales , la secuencia de sus decimales debe ser aleatoria en el sentido fuerte. $\ mathbb {R}$

Propiedades

La complejidad de Kolmogorov no es calculable . En otras palabras, no existe ningún programa de computadora que tome s como entrada y devuelva K ( s ). Para demostrarlo, razonemos por el absurdo y supongamos que tal función de Kolmo existe. Denotamos por k el tamaño de esta función (es decir, el número de caracteres de su código fuente). Entonces podríamos escribir el siguiente algoritmo:

n := 1 Tant que Kolmo(n) < k + 100 faire: n := n + 1 Fin du Tant que écrire n

Por lo tanto, este algoritmo escribe el número más pequeño para tener una complejidad de Kolmogorov mayor que k + 100 (este número necesariamente existe porque solo hay un número finito de programas de tamaño menor que k + 100 y hay una infinidad de números naturales).

Pero el algoritmo anterior está escrito precisamente con menos de k + 100 caracteres: por lo tanto, es de complejidad menor que k + 100, y escribe con precisión un número de complejidad mayor que k + 100, lo cual es absurdo (podemos acercar esta observación al argumento utilizado para la paradoja de Berry ).

Por tanto, no hay ninguna función que calcule la complejidad de Kolmogorov.

Variantes con recursos limitados

La definición de complejidad de Kolmogorov se define en términos del programa más pequeño que produce x. Pero este programa podría consumir importantes recursos. Por eso es importante tener en cuenta los recursos que utiliza el programa. Sea U una máquina universal. Aquí hay una versión limitada por el tiempo t:

${\ Displaystyle C ^ {t} (x) = \ min _ {p} \ {| p |: U (p) {\ text {escrito}} x {\ text {en}} t (| x |) { \ text {pasos}} \}}$

Se observará que la complejidad temporal se define en función de la salida x y no del tamaño del programa p. Sipser, en 1983, propuso una medida del tamaño del programa más pequeño que distingue una cadena de caracteres x. Buhrman, Fortnow y Laplante en 2002 dieron una versión no determinista, tomando una máquina universal no determinista. Se pueden encontrar otras definiciones en Levin , y en Allender donde la definición de complejidad es la suma de la complejidad de Kolmogorov y la contribución de la complejidad del tiempo.

Vínculo con la teoría de la complejidad algorítmica

Los vínculos entre la complejidad de Kolmogorov y la teoría de la complejidad se han establecido utilizando el siguiente conjunto como oráculo :

R = conjunto de cadenas de caracteres x cuya complejidad de Kolmogorov es al menos | x | / 2

En 2002, Allender Buhrman, Koucky van Melkebeek y Ronnerbuger muestran que PSPACE está incluido en P R y EXPTIME está incluido en NP R . A continuación, en 2004, Allender Buhrman, Koucky demostrar, usando las mismas técnicas que NEXPTIME está incluido en NP R .

Notas y referencias

Parte de este artículo (o una versión anterior) está adaptado de " Pequeño manual para el uso de agregados preparando el oral de modelado estocástico ", escrito por Djèlil Chafaï y publicado bajo GFDL .

Notas

Referencias

Andrey Kolmogorov , " Sobre tablas de números aleatorios ", Sankhyā Ser. A. , vol. 25,1963, p. 369–375 ( Revisiones de matemáticas 178484 )
Andrey Kolmogorov , " Sobre tablas de números aleatorios " , Informática teórica , vol. 207, n o 21998, p. 387–395 ( DOI 10.1016 / S0304-3975 (98) 00075-9 , Revisiones de matemáticas 1643414 )
Página de descripción del archivo en Wikimedia Commons .
(en-GB) Osamu Watanabe , Kolmogorov Complexity and Computational Complexity , coll. "Monografías de la EATCS sobre informática teórica",1992( ISBN 978-3-642-77737-0 , DOI 10.1007 / 978-3-642-77735-6 , leer en línea )
Michael Sipser , " Un enfoque teórico de la complejidad de la aleatoriedad ", Actas del Decimoquinto Simposio Anual de ACM sobre Teoría de la Computación , ACM, sTOC '83,1983, p. 330–335 ( ISBN 9780897910996 , DOI 10.1145 / 800061.808762 , leído en línea , consultado el 14 de julio de 2019 )
H. Buhrman , L. Fortnow y S. Laplante , “ Revisión de la complejidad de Kolmogorov limitada por recursos ”, SIAM Journal on Computing , vol. 31, n o 3,1 st de enero de de 2001, p. 887–905 ( ISSN 0097-5397 , DOI 10.1137 / S009753979834388X , leer en línea , consultado el 14 de julio de 2019 )
Eric Allender , " Cuando los mundos chocan: desaleatorización, límites inferiores y complejidad de Kolmogorov ", de reducciones, en "proc.29thacm Symposium on Theory of Computing ,1997, p. 730–738 ( lea en línea , consultado el 14 de julio de 2019 )
E. Allender , H. Buhrman , M. Koucky y D. van Melkebeek , “ Poder de cadenas aleatorias ”, 43º Simposio Anual de IEEE sobre Fundamentos de la Ciencia de la Computación, 2002. Actas. ,Noviembre de 2002, p. 669–678 ( DOI 10.1109 / SFCS.2002.1181992 , leído en línea , consultado el 14 de julio de 2019 )
(en) Eric Allender , Harry Buhrman y Michal Koucký , " ¿Qué se puede reducir eficientemente a las cadenas K-Random? » , STACS 2004 , Springer Berlin Heidelberg, notas de la conferencia en Ciencias de la Computación,2004, p. 584-595 ( ISBN 9783540247494 , DOI 10.1007 / 978-3-540-24749-4_51 , leído en línea , consultado el 14 de julio de 2019 )

Apéndices

Bibliografía

(fr) Gregory Chaitin Chance y complejidad en matemáticas, la búsqueda de Ω , Flammarion, enero de 2007 ( ISBN 2082105687 ) .
Ming Li y Paul Vitanyi. Introducción a la complejidad de Kolmogorov y sus aplicaciones. Springer Verlag 2008 ( ISBN 978-0-387-49820-1 )