7
$\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$

$\endgroup$
  • $\begingroup$ Does incompressible mean that the length of the string $s$ is a lower bound on its shortest description $K(s)$? $\endgroup$ – saadtaame Sep 16 '12 at 13:50
  • $\begingroup$ @saadtaame: it means that $K(s) \geq |s|$ $\endgroup$ – Vor Sep 16 '12 at 15:41
3
$\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)$.

$\endgroup$
  • $\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 Sep 17 '12 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 Sep 17 '12 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 Feb 21 '18 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. Feb 21 '18 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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