Kolmogorov-Komplexität der String-Verkettung

7

Wenn K(s)ist die Kolmogorov-Komplexität der Saites∈{0,1}∗,

Können wir die folgende Aussage beweisen (oder widerlegen):

"Jede Zeichenfolgesist ein Präfix einer inkompressiblen Zeichenfolge; dh für jede Saites Es gibt eine Zeichenfolge r so dass K(sr)≥|sr|"?

Sehr informell (und vielleicht nicht zu aussagekräftig): das wissen wir K(r)≤|r|+O(1);; wenn wir eine ausreichend große inkompressible Zeichenfolge auswählenrkönnen wir die "verwenden" O(1) um die Komprimierbarkeit der angegebenen Zeichenfolge zu "maskieren" s ?

Ein ähnliches (aber unterschiedliches) Ergebnis ist das für jedes c, wir können finden s und r so dass: K(sr)>K(s)+K(r)+c

computability kolmogorov-complexity Vor
quelle
Bedeutet inkompressibel, dass die Länge der Zeichenfolge s ist eine Untergrenze für die kürzeste Beschreibung K(s)?
Saadtaame
@saadtaame: das heißt das K(s)≥|s|
Vor dem

Antworten:

3

Ihre Vermutung ist falsch. Für einige KonstantenC,D, das hält es K(sr)≤2K(s)+K(r)+C≤2K(s)+|r|+D (Beweis: Verwenden Sie zum Generieren eine universelle Turingmaschine s und dann r;; du brauchst etwas mehr alsK(s)+K(r) um beide Programme zu speichern 2K(s)+K(r)ist ein Overkill). Deshalb wenn2K.(s)+D.<|s|, Ihre Vermutung hält nicht. So einfache Saitens sicherlich existieren zum Beispiel K.(0n)=Ö(Log⁡n).

Yuval Filmus
quelle
Es scheint okay zu sein. Ich dachte, dassD. kommt drauf an r, aber sobald die UTM behoben ist, ist sie eine Konstante. Eine weitere Überlegung: Bei der Verkettung der beiden Zeichenfolgen muss hinzugefügt werdenLog⁡|s| Bits (um das Programm für abzugrenzen s aus dem Programm für r), also funktioniert Ihr Beweis nicht, wenn wir die "Vermutung" in "jede inkompressible Zeichenfolge " änderns ist ein Präfix einer inkompressiblen Zeichenfolge r"? Können Sie sehen, wie man es leicht (dis) beweist?
Vor dem
Die letztere Vermutung ist seitdem weniger interessant sist schon inkompressibel. Formal können Sie wählenr=s, obwohl diese Lösung leicht zu verbieten ist.
Yuval Filmus
@ Yuval Filmus, haben Sie Ideen, wie Sie die zweite Aussage beweisen können, dh für jede c, wir können finden s und r so dass:
K.(sr)>K.(s)+K.(r)+c
Dies wird in Sipsers Buch angegeben und als Übungsproblem zurückgelassen, aber ich konnte es nicht beweisen, und ich bin sehr gespannt, welche Art von Beweistechnik verwendet werden sollte, um dieses Ergebnis zu zeigen. Vielen Dank!
Han Zhao
Ich schlage vor, dass Sie dies als neue Frage mit der Schaltfläche "Frage stellen" posten. Wenn Sie das tun, kann es hilfreich sein, wenn Sie uns mitteilen, welche Ansätze Sie versucht haben. Es gehört definitiv nicht als Antwort hierher.
DW