¿Existe x tal que K (xx) <K (x), donde K es la complementariedad de Kolmogorov.

Supongamos que denota la complejidad de Kolmogorov de una cadena . ¿Existe una cadena tal que . (Aquí es la concatenación de consigo mismo). Aquí se hizo una pregunta similar pero diferente , pero el contraejemplo dado en la respuesta a esa pregunta no funciona para esta. $K(x)$ $x$ $K(xx)<K(x)$ $xx$ $x$

cc.complexity-theory kolmogorov-complexity Sune Jakobsen
fuente

Respuestas:

No soy un experto en la complejidad de Kolmogorov, pero creo que tal x se puede construir para cada función de complejidad K de la siguiente manera. Como 1, 11, 1111, 11111111, ..., 1 ^{2 ⁿ} , ... es una codificación de un número natural n , K (1 ^{2 ⁿ} ) no puede ser o (log n ). Sin embargo, cuando n = 2 ^m , obviamente K (1 ^{2 ⁿ} ) = K (1 ^{2 ^{2 ^m}} ) = O (log m ) = O (log log n ). Por lo tanto, la secuencia K (1), K (11), K (1111), K (11111111), ..., K (1 ^{2 ⁿ} ), ... no puede aumentar débilmente monotónicamente, lo que significa que existe una cadenax en la forma 1 ^{2 ⁿ} tal que K ( xx) <K ( x ).

Tsuyoshi Ito
fuente

@ Tsuyoshi, ¿Hay una cadena incompresible

tal que

x

$x$

K (x x) < K (x)

$K(xx)\lt K(x)$

Mohammad Al-Turkistany

Creo que

y K (1 ^ {2 ^ n}) = Ω (log n) se contradicen entre sí. Lo que quiere decir es: si

entonces

. De lo contrario, la prueba parece estar bien.

K (1^{2^{2^{m}}}) = O (\log m)

$K(1^{2^{2^m}})=O(\log m)$

f (n) = o (\log n)

$f(n)=o(\log n)$

K (1^{2^{n}}) \neq O (f (n))

$K(1^{2^n})\neq O(f(n))$

Sune Jakobsen

Esto parece funcionar. De hecho, creo que te da una secuencia infinita de tales cadenas. Sin embargo, o estoy malinterpretando algo, o la declaración de la regla de la cadena para la Complejidad de Kolmogorov que aparece en wikipedia ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ) es incorrecta. Inicialmente pensé que la definición de Wikipedia podría no aplicarse aquí, ya que allí debes saber dónde termina X e Y, mientras que aquí parece no ser necesario, pero cuando Y = X puedes agregar eso a la descripción en O (1) diciendo "dividido en el medio".

Abel Molina

@Sune: La notación Ω (⋅) tiene varias definiciones ligeramente diferentes. "K (1 ^ 2 ^ n) = Ω (log n)" en mi respuesta significa "limsup K (1 ^ 2 ^ n) / log n> 0", y no contradice "K (1 ^ 2 ^ 2 ^ m) = O (log m) ”. Edité la respuesta para aclarar este punto. Ver también ¿Qué definición de tasa de crecimiento asintótica debemos enseñar?

Tsuyoshi Ito

@turkistany y todo: tenga en cuenta que siempre es cierto que K (xx)> K (x) -c para alguna constante, pensé que esto debería señalarse. Esto también significa que necesitamos una definición muy precisa de incompresible si queremos estudiar esta pregunta. Supongo que la respuesta es sí, pero no tengo una prueba.

domotorp

Si. La complejidad de Kolomogorov en la práctica depende de su modelo. Máquina de Turing, programa Java, programa C ++, ... si hay una idiosincrasia en su modelo que permita que esto suceda en un conjunto finito de entradas, no hay problema.

La mejor pregunta es cuánto de este comportamiento puede salirse con la suya y todavía hacer que el modelo sea universal.

Chad Brewbaker
fuente

Creo que una mejor pregunta es: ¿existe tal x para todos los modelos? No sé qué es un "modelo" formalmente, pero parece que la respuesta de Tsuyoshis funciona para todos los lenguajes de programación razonables.

Sune Jakobsen

Puede asignar

y algo más grande para

y todavía tener un modelo universal.

0

$0$

x x

$xx$

x

$x$

Kaveh

@ Tsuyoshi:

No entendí bien tu prueba.

Supongamos que elegir una máquina de Turing estándar como "lenguaje de descripción de" definición de como el número de estados de la TM más pequeño que se inicia con una cinta vacía y se detiene después de imprimir la cadena en ella. $K(s)$ $s$

$TM_{ss}$ $ss = 1111...1 = 1^{2^{n+1}}$ $TM_{s}$ $s = 1^{2^n}$ ?

¿Se puede aplicar su prueba a la complejidad de Kolmogorov en TM?

$n+1 = 2^{m}$ $TM_{ss}$ $TM_{s}$ $n$

(lo siento, pero no sé cómo publicar esto como comentario)

Marzio De Biasi
fuente

Para escribir un comentario en una publicación realizada por alguien que no sea usted y que no sea una respuesta a su pregunta, necesita un punto de reputación de al menos 50.

Tsuyoshi Ito