Gibt es x mit K (xx) <K (x), wobei K die Kolmogorov-Komplexität ist?

Sei die Kolmogorov-Komplexität einer Zeichenkette . Haben gibt es eine Zeichenfolge , so dass . (Hier ist die Verkettung von mit sich selbst). Eine ähnliche, aber unterschiedliche Frage wurde hier gestellt , aber das in der Antwort auf diese Frage angegebene Gegenbeispiel funktioniert für diese Frage nicht. $K(x)$ $x$ $K(xx)<K(x)$ $xx$ $x$

cc.complexity-theory kolmogorov-complexity Sune Jakobsen
quelle

Antworten:

Ich bin kein Experte für Kolmogorov-Komplexität, aber ich denke, dass ein solches x für jede Komplexitätsfunktion K wie folgt konstruiert werden kann. Da 1, 11, 1111, 11111111,…, 1 ^{2 ⁿ} ,… eine Kodierung einer natürlichen Zahl n ist , kann K (1 ^{2 ⁿ} ) nicht o (log n ) sein. Wenn jedoch n = 2 ^{m ist} , ist offensichtlich K (1 ^{2 ⁿ} ) = K (1 ^{2 ^{2 ^m}} ) = O (log m ) = O (log log n ). Daher kann die Sequenz K (1), K (11), K (1111), K (11111111), ..., K (1 ^{2 ⁿ} ), ... nicht schwach monoton ansteigen, was bedeutet, dass eine Kette existiertx in der Form 1 ^{2 ^n,} so dass K ( xx ) <K ( x ) ist.

Tsuyoshi Ito
quelle

@ Tsuyoshi, Gibt es eine inkompressible Zeichenkette

so dass

x

$x$

K (x x) < K (x)

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

Mohammad Al-Turkistany

Ich denke, dass

und K (1 ^ {2 ^ n}) = Ω (log n) sich widersprechen. Was er meint ist: Wenn

dann ist

. Ansonsten scheint der Beweis in Ordnung.

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

Das scheint zu funktionieren. In der Tat denke ich, es gibt Ihnen eine unendliche Folge solcher Zeichenfolgen. Entweder verstehe ich jedoch etwas falsch oder die Aussage der Kettenregel für Kolmogorov-Komplexität, die in Wikipedia ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ) erscheint, ist dann falsch. Anfangs dachte ich, dass die Definition von Wikipedia hier nicht zutreffen könnte, da man wissen muss, wo X endet und Y beginnt, während dies hier nicht erforderlich zu sein scheint, aber wenn Y = X, kann man das der Beschreibung in hinzufügen O (1) mit "Split in the Middle".

Abel Molina

@Sune: Die Notation Ω (⋅) hat einige leicht unterschiedliche Definitionen. "K (1 ^ 2 ^ n) = Ω (log n)" in meiner Antwort bedeutet "limsup K (1 ^ 2 ^ n) / log n> 0" und widerspricht nicht "K (1 ^ 2 ^ 2" ^ m) = O (log m). “Ich habe die Antwort bearbeitet, um diesen Punkt zu verdeutlichen. Siehe auch Welche Definition der asymptotischen Wachstumsrate sollten wir vermitteln?

Tsuyoshi Ito

@turkistany und alle: Beachten Sie, dass es immer wahr ist, dass K (xx)> K (x) -c für eine Konstante, ich dachte, dies sollte darauf hingewiesen werden. Dies bedeutet auch, dass wir eine sehr genaue Definition von inkompressibel benötigen, wenn wir diese Frage untersuchen wollen. Ich würde vermuten, dass die Antwort wieder Ja lautet, aber ich habe keinen Beweis.

Domotorp

Ja. Die Komplexität von Kolomogorov in der Praxis hängt von Ihrem Modell ab. Turing-Maschine, Java-Programm, C ++ - Programm, ... Wenn Ihr Modell eine Eigenart aufweist, die dies für eine begrenzte Anzahl von Eingaben zulässt, ist dies kein Problem.

Die bessere Frage ist, mit wie viel von diesem Verhalten Sie durchkommen und das Modell dennoch universell sein lassen können.

Chad Brewbaker
quelle

Ich denke, eine bessere Frage ist: Gibt es ein solches x für alle Modelle? Ich weiß nicht, was ein "Modell" formal ist, aber es scheint, dass Tsuyoshis Antwort für alle vernünftigen Programmiersprachen funktioniert.

Sune Jakobsen

0

$0$

x x

$xx$

x

$x$

@ Tsuyoshi:

Ich habe deinen Beweis nicht gut verstanden.

$K(s)$ $s$

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

Kann Ihr Beweis auf die Komplexität von Kolmogorov auf TMs angewendet werden?

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

(Entschuldigung, aber ich weiß nicht, wie ich das als Kommentar posten soll)

Marzio De Biasi
quelle

Um einen Kommentar zu einem Beitrag von jemand anderem als Ihnen zu verfassen , der keine Antwort auf Ihre Frage darstellt, benötigen Sie einen Rufpunkt von mindestens 50.

Tsuyoshi Ito