8
$\begingroup$

If $K(s)$ is the Kolmogorov complexity of the string $s \in \{0,1\}^*$,

Can we prove (or disprove) the following statement:

"Every string $s$ is a prefix of an incompressible string; i.e. for every string $s$ there exists a string $r$ such that $K(sr) \geq |sr|$" ?

In a very informal (and perhaps not too meaningful) way: we know that $K(r) \leq |r| + O(1)$; if we pick a large enough incompressible string $r$, can we "use" the $O(1)$ to "mask" the compressibility of the given string $s$ ?

A similar (but different) result is that for any $c$, we can find $s$ and $r$ such that: $K(sr) > K(s) + K(r) + c$

Improve this question
$\endgroup$
2
  • $\begingroup$ Does incompressible mean that the length of the string $s$ is a lower bound on its shortest description $K(s)$? $\endgroup$
    – mrk
    Commented Sep 16, 2012 at 13:50
  • $\begingroup$ @saadtaame: it means that $K(s) \geq |s|$ $\endgroup$
    – Vor
    Commented Sep 16, 2012 at 15:41

1 Answer 1

Reset to default
4
$\begingroup$

Your conjecture is wrong. For some constants $C,D$, it holds that $K(sr) \leq 2K(s) + K(r) + C \leq 2K(s) + |r| + D$ (proof: use a universal Turing machine to generate $s$ and then $r$; you need somewhat more than $K(s)+K(r)$ to store both programs, though $2K(s)+K(r)$ is an overkill). Therefore if $2K(s) + D < |s|$, your conjecture doesn't hold. Such easy strings $s$ certainly exist, for example $K(0^n) = O(\log n)$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ it seems ok. I thought that $D$ depends on $r$, but once fixed the UTM it is a constant. Another consideration: in concatenating the two strings one must add $\log |s|$ bits (to delimit the program for $s$ from the program for $r$), so your proof doesn't work if we modify the "conjecture" into: "every incompressible string $s$ is a prefix of an incompressible string $r$"? Can you see how to (dis)prove it easily? $\endgroup$
    – Vor
    Commented Sep 17, 2012 at 8:55
  • $\begingroup$ The latter conjecture is less interesting since $s$ is already incompressible. Formally, you could choose $r = s$, though this solution is easy to disallow. $\endgroup$
    – Yuval Filmus
    Commented Sep 17, 2012 at 14:55
  • $\begingroup$ @Yuval Filmus, do you have any ideas on how to prove the second statement, i.e., for any $c$, we can find $s$ and $r$ such that: $$K(sr)>K(s)+K(r)+c$$ This is stated in Sipser's book and left as an exercise problem, but I was not able to prove it, and I am very curious to know what kind of proof technique should be used to show this result. Thanks! $\endgroup$
    – Han Zhao
    Commented Feb 21, 2018 at 0:45
  • $\begingroup$ I suggest you post this as a new question with the 'Ask Question' button. When you do that, it might help if you told us what approaches you tried. It definitely doesn't belong as an answer here. $\endgroup$
    – D.W. ♦
    Commented Feb 21, 2018 at 1:06
  • 1
    $\begingroup$ The book considers both definitions. The more usual one is not self-delimiting. $\endgroup$
    – Yuval Filmus
    Commented Apr 19, 2022 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.