Complejidad de Kolmogorov

Esta imagen ilustra parte del conjunto Mandelbrot fractal. Simplemente almacenar el color de 24 bits de cada píxel en esta imagen requeriría 23 millones de bytes, pero un pequeño programa informático puede reproducir estos 23 MB utilizando la definición del conjunto Mandelbrot y las coordenadas de esquina de la imagen. Así, la complejidad de Kolmogorov de esta imagen es mucho menos de 23 MB en cualquier modelo pragmático de computación. La compresión de imagen para uso general de PNG sólo reduce a 1,6 MB, más pequeña que los datos brutos, pero mucho más grande que la complejidad de Kolmogorov.

En la teoría algorítmica de la información (un subcampo de las ciencias de la computación y las matemáticas), la complejidad de Kolmogorov de un objeto, como un fragmento de texto, es la longitud de un programa de computadora más corto (en un formato predeterminado). lenguaje de programación) que produce el objeto como salida. Es una medida de los recursos computacionales necesarios para especificar el objeto, y también se conoce como complejidad algorítmica, complejidad de Solomonoff-Kolmogorov-Chaitin, complejidad del tamaño del programa , complejidad descriptiva o entropía algorítmica. Lleva el nombre de Andrey Kolmogorov, quien publicó por primera vez sobre el tema en 1963 y es una generalización de la teoría clásica de la información.

La noción de complejidad de Kolmogorov se puede utilizar para enunciar y probar resultados de imposibilidad similares al argumento diagonal de Cantor, el teorema de incompletitud de Gödel y el problema de detención de Turing. En particular, ningún programa P que calcule un límite inferior para la complejidad de Kolmogorov de cada texto puede devolver un valor esencialmente mayor que la propia longitud de P (ver sección § Teorema de incompletitud de Chaitin); por lo tanto, ningún programa único puede calcular la complejidad exacta de Kolmogorov para una cantidad infinita de textos.

Definición

Considere las siguientes dos cadenas de 32 letras minúsculas y dígitos:

abababababababababababababababab y

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

La primera cadena tiene una breve descripción en inglés, a saber, "escribir ab 16 veces", que consta de 17 caracteres. El segundo no tiene una descripción simple obvia (usando el mismo conjunto de caracteres) además de escribir la cadena en sí, es decir, "write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" que tiene 38 caracteres. Por lo tanto, se puede decir que la operación de escribir la primera cadena tiene "menos complejidad" que escribir el segundo.

Más formalmente, la complejidad de una cadena es la longitud de la descripción más breve posible de la cadena en algún lenguaje de descripción universal fijo (la sensibilidad de la complejidad relativa a la elección del lenguaje de descripción se analiza a continuación). Se puede demostrar que la complejidad de Kolmogorov de cualquier cadena no puede ser más de unos pocos bytes mayor que la longitud de la propia cadena. Las cadenas como el ejemplo anterior de abab, cuya complejidad de Kolmogorov es pequeña en relación con el tamaño de la cadena, no se consideran complejas.

La complejidad de Kolmogorov se puede definir para cualquier objeto matemático, pero por simplicidad, el alcance de este artículo se restringe a las cadenas. Primero debemos especificar un lenguaje de descripción para las cadenas. Dicho lenguaje de descripción puede basarse en cualquier lenguaje de programación de computadoras, como Lisp, Pascal o Java. Si P es un programa que genera una cadena x, entonces P es una descripción de x. La longitud de la descripción es solo la longitud de P como una cadena de caracteres, multiplicada por la cantidad de bits en un carácter (por ejemplo, 7 para ASCII).

Podríamos, alternativamente, elegir una codificación para máquinas de Turing, donde una codificación es una función que asocia a cada Máquina de Turing M una cadena de bits <M >. Si M es una máquina de Turing que, en la entrada w, genera la cadena x, entonces la cadena concatenada <M> w es una descripción de x. Para el análisis teórico, este enfoque es más adecuado para la construcción de pruebas formales detalladas y, en general, se prefiere en la literatura de investigación. En este artículo, se discute un enfoque informal.

Cualquier cadena s tiene al menos una descripción. Por ejemplo, la segunda cadena anterior se genera mediante el pseudocódigo:

función GenerateString2()
 retorno "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

mientras que la primera cadena se genera mediante el pseudocódigo (mucho más corto):

función GenerateString1()
 retorno "ab" × 16

Si una descripción d(s) de una cadena s tiene una longitud mínima (es decir, usa la menor cantidad de bits), es llamado una descripción mínima de s, y la longitud de d(s) (es decir, el número de bits en la descripción mínima) es la complejidad de Kolmogorov de s, escrita K(s). Simbólicamente,

K()s.d()s.

La longitud de la descripción más corta dependerá de la elección del lenguaje de descripción; pero el efecto de cambiar de idioma está acotado (un resultado llamado teorema de invariancia).

Teorema de invariancia

Trato informal

Hay algunos lenguajes de descripción que son óptimos, en el siguiente sentido: dada cualquier descripción de un objeto en un lenguaje de descripción, dicha descripción puede usarse en el lenguaje de descripción óptimo con una sobrecarga constante. La constante depende solo de los lenguajes involucrados, no de la descripción del objeto, ni del objeto que se describe.

Este es un ejemplo de un lenguaje de descripción óptimo. Una descripción tendrá dos partes:

• La primera parte describe otro lenguaje de descripción.
• La segunda parte es una descripción del objeto en ese idioma.

En términos más técnicos, la primera parte de una descripción es un programa de computadora (específicamente: un compilador para el lenguaje del objeto, escrito en el lenguaje de descripción), y la segunda parte es la entrada a ese programa de computadora. que produce el objeto como salida.

El teorema de invariancia es el siguiente: Dado cualquier lenguaje de descripción L, el lenguaje de descripción óptimo es al menos tan eficiente como L, con alguna constante gastos generales.

Prueba: Cualquier descripción D en L se puede convertir en una descripción en el lenguaje óptimo describiendo primero L como un programa de computadora P (parte 1), y luego usar la descripción original D como entrada para ese programa (parte 2). Él la longitud total de esta nueva descripción D′ es (aproximadamente):

SilencioD′ SilencioPSilenciosoDSilencio

La longitud de P es una constante que no depende de D. Entonces, como mucho, hay una sobrecarga constante, independientemente del objeto descrito. Por tanto, el lenguaje óptimo es universal hasta esta constante aditiva.

Un trato más formal

Teorema: Si K₁ y K₂ son las funciones de complejidad en relación con los lenguajes de descripción completa de Turing L₁ y L₂, entonces hay una constante c, que depende solo de los idiomas L₁ y L₂ elegidos, de modo que

Оs. −c ≤ K₁()s) − K₂()s≤ c.

Prueba: Por simetría, basta probar que existe alguna constante c tal que para todas las cadenas s

K₁()s≤ K₂()s) + c.

Ahora, supongamos que existe un programa en el lenguaje L₁ que actúa como intérprete de L₂:

función InterpretLanguage(cuerda p)

donde p es un programa en L₂. El intérprete se caracteriza por la siguiente propiedad:

Corriendo InterpretLanguage sobre la entrada p devuelve el resultado de correr p.

Por lo tanto, si P es un programa en L₂ que es una descripción mínima de s, entonces InterpretLanguage(P) devuelve la cadena s. La longitud de esta descripción de s es la suma de

1. La longitud del programa InterpretLanguage, que podemos tomar para ser la constante c.
2. La longitud P que por definición K₂()s).

Esto demuestra el límite superior deseado.

Historia y contexto

La teoría algorítmica de la información es el área de la informática que estudia la complejidad de Kolmogorov y otras medidas de complejidad en cadenas (u otras estructuras de datos).

El concepto y la teoría de la complejidad de Kolmogorov se basan en un teorema crucial descubierto por primera vez por Ray Solomonoff, quien lo publicó en 1960 y lo describió en "Informe preliminar sobre una teoría general de la inferencia inductiva" como parte de su invención de la probabilidad algorítmica. Dio una descripción más completa en sus publicaciones de 1964, "Una teoría formal de la inferencia inductiva", Parte 1 y Parte 2 en Información y Control.

Andrey Kolmogorov más tarde publicó de forma independiente este teorema en Problems Inform. Transmission en 1965. Gregory Chaitin también presenta este teorema en J. ACM – El documento de Chaitin se presentó en octubre de 1966 y se revisó en diciembre de 1968, y cita los documentos de Solomonoff y Kolmogorov.

El teorema dice que, entre los algoritmos que decodifican cadenas a partir de sus descripciones (códigos), existe uno óptimo. Este algoritmo, para todas las cadenas, permite códigos tan cortos como lo permite cualquier otro algoritmo hasta una constante aditiva que depende de los algoritmos, pero no de las cadenas en sí. Solomonoff usó este algoritmo y las longitudes de código que permite definir una "probabilidad universal" de una cadena en la que se puede basar la inferencia inductiva de los dígitos subsiguientes de la cadena. Kolmogorov usó este teorema para definir varias funciones de cadenas, incluida la complejidad, la aleatoriedad y la información.

Cuando Kolmogorov se enteró del trabajo de Solomonoff, reconoció la prioridad de Solomonoff. Durante varios años, el trabajo de Solomonoff fue más conocido en la Unión Soviética que en el mundo occidental. El consenso general en la comunidad científica, sin embargo, fue asociar este tipo de complejidad con Kolmogorov, quien se preocupaba por la aleatoriedad de una secuencia, mientras que la probabilidad algorítmica se asoció con Solomonoff, quien se centró en la predicción utilizando su invención de la distribución de probabilidad previa universal.. El área más amplia que abarca la complejidad descriptiva y la probabilidad a menudo se denomina complejidad de Kolmogorov. El informático Ming Li considera esto un ejemplo del efecto Mateo: "...a todo el que tiene, más se le dará..."

Hay varias otras variantes de la complejidad de Kolmogorov o información algorítmica. El más utilizado se basa en programas autodelimitantes y se debe principalmente a Leonid Levin (1974).

Mark Burgin introdujo un enfoque axiomático de la complejidad de Kolmogorov basado en los axiomas de Blum (Blum 1967) en el artículo presentado para su publicación por Andrey Kolmogorov.

Resultados básicos

En la siguiente discusión, sea K(s) la complejidad de la cadena s.

No es difícil ver que la descripción mínima de una cadena no puede ser mucho más grande que la propia cadena: el programa GenerateString2 anterior que genera s es un programa fijo cantidad mayor que s.

Teorema: Existe una constante c tal que

Оs. K()s≤sSilencio + c.

Incomputabilidad de la complejidad de Kolmogorov

Un intento ingenuo de un programa para calcular K

A primera vista, puede parecer trivial escribir un programa que pueda calcular K(s) para cualquier s, como el siguiente:

función KolmogorovComplexity(cuerda s)
 para i = 1 a infinito:
 para cada uno string de longitud exactamente
 si isValidProgram(p) y (p) == s
 retorno i

Este programa itera a través de todos los programas posibles (recorriendo todas las cadenas posibles y considerando solo aquellos que son programas válidos), comenzando con el más corto. Cada programa se ejecuta para encontrar el resultado producido por ese programa, comparándolo con la entrada s. Si el resultado coincide, se devuelve la duración del programa.

Sin embargo, esto no funcionará porque algunos de los programas p probados no terminarán, p. si contienen bucles infinitos. No hay forma de evitar todos estos programas probándolos de alguna manera antes de ejecutarlos debido a la no computabilidad del problema de detención.

Además, ningún programa puede calcular la función K, por muy sofisticado que sea. Esto se demuestra a continuación.

Prueba formal de incomputabilidad de K

Teorema: existen cadenas de complejidad de Kolmogorov arbitrariamente grande. Formalmente: para cada número natural n, existe una cadena s con K(s) ≥ n.

Prueba: De lo contrario, la cantidad infinita de cadenas finitas posibles podría generarse mediante la cantidad finita de programas con una complejidad inferior a n bits.

Teorema: K no es una función computable. En otras palabras, no hay ningún programa que tome cualquier cadena s como entrada y produzca el entero K(s) como salida.

La siguiente prueba por contradicción usa un lenguaje simple similar a Pascal para denotar programas; en aras de la simplicidad de la prueba, suponga que su descripción (es decir, un intérprete) tiene una longitud de 1400000 bits. Supongamos por contradicción que hay un programa

función KolmogorovComplexity(cuerda s)

que toma como entrada una cadena s y devuelve K(s). Todos los programas tienen una longitud finita, por lo que, en aras de la simplicidad de la prueba, asuma que es 7000000000 bits. Ahora, considere el siguiente programa de longitud 1288 bits:

función GenerateComplexString()
 para i = 1 a infinito:
 para cada uno cuerda de longitud exactamente
 si KolmogorovComplexity(s) ≥ 8000000000
 retorno s

Usando KolmogorovComplexity como subrutina, el programa prueba cada cadena, comenzando con la más corta, hasta que devuelve una cadena con una complejidad de Kolmogorov al menos 8000000000 bits, es decir, una cadena que no puede ser producida por ningún programa más corta que 8000000000 bits. Sin embargo, la longitud total del programa anterior que produjo s es solo 7001401288 bits, lo cual es una contradicción. (Si el código de KolmogorovComplexity es más corto, la contradicción permanece. Si es más largo, la constante utilizada en GenerateComplexString siempre se puede cambiar adecuadamente).

La prueba anterior utiliza una contradicción similar a la de la paradoja de Berry: "₁La ₂menor ₃positivo ₄entero ₅que ₆no puede ₇ser ₈definido ₉en ₁₀menos ₁₁que ₁₂ veinte ₁₃Inglés ₁₄palabras". También es posible mostrar la no computabilidad de K mediante la reducción de la no computabilidad del problema de detención H, ya que K y H son equivalentes de Turing.

Hay un corolario, llamado con humor el "teorema de pleno empleo" en la comunidad de lenguajes de programación, afirmando que no existe un compilador de optimización de tamaño perfecto.

Regla de la cadena para la complejidad de Kolmogorov

La regla de la cadena para la complejidad de Kolmogorov establece que

K()X,Y≤ K()X) + K()YSilencioX) + O(log(K()X,Y)).

Establece que el programa más corto que reproduce X e Y no es más que un término logarítmico mayor que un programa para reproducir X y un programa para reproducir Y dado X. Usando esta declaración, uno puede definir un análogo de información mutua para la complejidad de Kolmogorov.

Compresión

Es sencillo calcular los límites superiores para K(s): simplemente comprima la cadena s con algún método, implemente el descompresor correspondiente en el idioma elegido, concatene el descompresor a la cadena comprimida y mida la longitud de la cadena resultante, concretamente, el tamaño de un archivo autoextraíble en el idioma dado.

Una cadena s es comprimible por un número c si tiene una descripción cuya longitud no exceda |s| − bits c. Esto es equivalente a decir que K(s) ≤ |s| − c. De lo contrario, s es incompresible por c. Se dice que una cadena incompresible por 1 es simplemente incompresible - según el principio del casillero, que se aplica porque cada cadena comprimida se asigna a una sola cadena sin comprimir, las cadenas incompresibles deben existir, ya que hay 2ⁿ cadenas de bits de longitud n, pero solo 2ⁿ − 1 cadenas más cortas, es decir, cadenas de longitud menor que n, (es decir, con longitud 0, 1,..., n − 1).

Por la misma razón, la mayoría de las cadenas son complejas en el sentido de que no pueden comprimirse significativamente: su K(s) no es mucho más pequeña que | s|, la longitud de s en bits. Para hacer esto preciso, fije un valor de n. Hay 2ⁿ cadenas de bits de longitud n. La distribución de probabilidad uniforme en el espacio de estas cadenas de bits asigna exactamente el mismo peso 2⁻ⁿ a cada cadena de longitud n.

Teorema: Con la distribución de probabilidad uniforme en el espacio de cadenas de bits de longitud n, la probabilidad de que una cadena sea incompresible por c es al menos 1 − 2^−c+1 + 2⁻ⁿ.

Para probar el teorema, tenga en cuenta que el número de descripciones de longitud que no exceda n − c está dado por la serie geométrica:

1 + 2 + 2² +... + 2^{n − c} = 2^{n−c+ 1} − 1.

Quedan al menos

2ⁿ − 2^{n−c+ 1} + 1

cadenas de bits de longitud n que son incompresibles por c. Para determinar la probabilidad, divida por 2ⁿ.

Teorema de incompletitud de Chaitin

Complejidad Kolmogorov K()s), y dos funciones inferiores computables prog1(s), prog2(s). El eje horizontal (escala logarítmica) enumera todas las cuerdas s, ordenado por longitud; el eje vertical (escala lineal) mide la complejidad de Kolmogorov en pedazos. La mayoría de las cadenas son incompresibles, es decir, su complejidad de Kolmogorov excede su longitud por una cantidad constante. 9 cadenas compresibles se muestran en la imagen, apareciendo como pendientes casi verticales. Debido al teorema incompleto de Chaitin (1974), la salida de cualquier programa que computa un límite inferior de la complejidad de Kolmogorov no puede exceder algún límite fijo, que es independiente de la cadena de entrada s.

Según el teorema anterior (§ Compresión), la mayoría de las cadenas son complejas en el sentido de que no se pueden describir de ninguna forma significativamente "comprimida" forma. Sin embargo, resulta que el hecho de que una cadena específica sea compleja no se puede probar formalmente si la complejidad de la cadena está por encima de cierto umbral. La formalización precisa es la siguiente. Primero, fije un sistema axiomático particular S para los números naturales. El sistema axiomático tiene que ser lo suficientemente potente para que, a ciertas afirmaciones A sobre la complejidad de las cadenas, se pueda asociar una fórmula F_A en S. Esta asociación debe tener la siguiente propiedad:

Si F_A es demostrable a partir de los axiomas de S, entonces la afirmación correspondiente A debe ser verdadero. Esta "formalización" se puede lograr en base a una numeración de Gödel.

Teorema: Existe una constante L (que solo depende de S y de la elección del lenguaje de descripción) tal que no existe una cadena s para la cual la declaración

K()s) ≥ L (como formalizado en S)

puede probarse dentro de S.

Idea de prueba: la prueba de este resultado se basa en una construcción autorreferencial utilizada en la paradoja de Berry. Primero obtenemos un programa que enumera las pruebas dentro de S y especificamos un procedimiento P que toma como entrada un número entero L e imprime las cadenas x que están dentro de las pruebas dentro de S del enunciado K(x) ≥ L. Al establecer L en un valor mayor que la longitud de este procedimiento P, tenemos que la longitud requerida de un programa para imprimir x como se indica en K(x) ≥ L siendo al menos L entonces menor que la cantidad L ya que la cadena x fue impresa por el procedimiento P. Esto es una contradicción. Entonces no es posible que el sistema de prueba S demuestre K(x) ≥ L para L arbitrariamente grande, en particular, para L mayor que la longitud del procedimiento P, (que es finito).

Prueba:

Podemos encontrar una enumeración efectiva de todas las pruebas formales en S por algún procedimiento

función NthProof(int n)

que toma como entrada n y genera alguna prueba. Esta función enumera todas las pruebas. Algunas de estas son pruebas para fórmulas que no nos interesan aquí, ya que todas las pruebas posibles en el lenguaje de S se producen para algún n. Algunas de estas son fórmulas de complejidad de la forma K(s) ≥ n donde s y n son constantes en el lenguaje de S. hay un procedimiento

función NthProofProvesComplexityFormula(int n)

que determina si la prueba nésima realmente prueba una fórmula de complejidad K(s) ≥ L. Las cadenas s, y el entero L a su vez, son computables por procedimiento:

función StringNthProof(int n)

función ComplejidadLowerBoundNthProof(()int n)

Considere el siguiente procedimiento:

función GenerarProporcionableComplexString(int n)
 para i = 1 al infinito:
 si NthProofProvesComplexityFormula(i) y ComplejidadLowerBoundNthProof(i) ≥ n retorno StringNthProof(i)

Dado un n, este procedimiento prueba todas las pruebas hasta que encuentra una cadena y una prueba en el sistema formal S de la fórmula K (s) ≥ L para algunos L ≥ n; si no existe tal prueba, se repite para siempre.

Finalmente, considere el programa que consta de todas estas definiciones de procedimientos y una llamada principal:

GenerarProporcionableComplexString(n0)

donde la constante n₀ se determinará más adelante. La duración total del programa se puede expresar como U+log₂(n₀), donde U es una constante y log₂(n₀) representa la longitud del valor entero n ₀, bajo la suposición razonable de que está codificado en dígitos binarios. Elegiremos n₀ mayor que la duración del programa, es decir, tal que n₀ > U+log₂(n₀). Esto es claramente cierto para n₀ lo suficientemente grande, porque el lado izquierdo crece linealmente en n₀ mientras que el lado izquierdo crece linealmente en n₀ mientras que el el lado derecho crece logarítmicamente en n₀ hasta la constante fija U.

Entonces no hay prueba de la forma "K(s)≥L" con L≥n₀ se puede obtener en S, como se puede ver por un argumento indirecto: Si ComplexityLowerBoundNthProof(i) pudiera devolver un valor ≥n₀, entonces el ciclo dentro de GenerateProvablyComplexString eventualmente terminaría, y ese procedimiento devolvería una cadena s tal que

Esto es una contradicción, Q.E.D.

Como consecuencia, el programa anterior, con el valor elegido de n₀, debe repetirse para siempre.

Se utilizan ideas similares para probar las propiedades de la constante de Chaitin.

Longitud mínima del mensaje

El principio de longitud mínima de mensaje de inferencia estadística e inductiva y aprendizaje automático fue desarrollado por C.S. Wallace y D.M. Boulton en 1968. MML es bayesiano (es decir, incorpora creencias anteriores) y teórico de la información. Tiene las propiedades deseables de invariancia estadística (es decir, la inferencia se transforma con una reparametrización, como de coordenadas polares a coordenadas cartesianas), consistencia estadística (es decir, incluso para problemas muy difíciles, MML convergerá a cualquier modelo subyacente) y eficiencia (es decir, el modelo MML convergerá a cualquier modelo subyacente verdadero tan pronto como sea posible). C. S. Wallace y D. L. Dowe (1999) mostró una conexión formal entre MML y la teoría algorítmica de la información (o complejidad de Kolmogorov).

Aleatoriedad de Kolmogorov

La aleatoriedad de Kolmogorov define una cadena (generalmente de bits) como aleatoria si y solo si cada programa de computadora que puede producir esa cadena es al menos tan largo como la propia cadena. Para que esto sea preciso, se debe especificar una computadora universal (o máquina de Turing universal), de modo que "program" significa un programa para esta máquina universal. Una cadena aleatoria en este sentido es "incompresible" en que es imposible "comprimir" la cadena en un programa que es más corto que la propia cadena. Para cada computadora universal, hay al menos una cadena algorítmicamente aleatoria de cada longitud. Sin embargo, si una cadena en particular es aleatoria, depende de la computadora universal específica que se elija. Esto se debe a que una computadora universal puede tener una cadena particular codificada en sí misma, y un programa que se ejecuta en esta computadora universal puede simplemente referirse a esta cadena codificada usando una secuencia corta de bits (es decir, mucho más corta que la cadena misma).

Esta definición se puede extender para definir una noción de aleatoriedad para secuencias infinitas de un alfabeto finito. Estas secuencias algorítmicamente aleatorias se pueden definir de tres formas equivalentes. Una forma usa un análogo efectivo de la teoría de la medida; otro usa martingalas efectivas. La tercera forma define que una secuencia infinita es aleatoria si la complejidad de Kolmogorov sin prefijo de sus segmentos iniciales crece lo suficientemente rápido; debe haber una constante c tal que la complejidad de un segmento inicial de longitud n siempre es al menos n−c. Esta definición, a diferencia de la definición de aleatoriedad para una cadena finita, no se ve afectada por la máquina universal que se utiliza para definir la complejidad de Kolmogorov sin prefijos.

Relación con la entropía

Para los sistemas dinámicos, la tasa de entropía y la complejidad algorítmica de las trayectorias están relacionados por un teorema de Brudno, que la igualdad K()x;T)=h()T){displaystyle K(x;T)=h(T)} para casi todo x{displaystyle x}.

Se puede demostrar que para la salida de las fuentes de información de Markov, la complejidad de Kolmogorov está relacionada con la entropía de la fuente de información. Más precisamente, la complejidad de Kolmogorov de la salida de una fuente de información de Markov, normalizada por la longitud de la salida, converge casi con seguridad (ya que la longitud de la salida tiende a infinito) a la entropía de la fuente.

Versiones condicionales

La complejidad condicional de Kolmogorov de dos cuerdas K()xSilencioSí.){displaystyle K(x toleray)} es, aproximadamente, definida como la complejidad de Kolmogorov x dado Sí. como entrada auxiliar al procedimiento.

También hay una complejidad larga-condicional K()xSilencioL()x)){displaystyle K(x habitL(x)}, que es la complejidad de x dada la longitud x como conocido / entrada.