[Solved]: Kolmogorov complexity of string concatenation

Problem Detail: 

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$

Asked By : Vor

Answered By : Yuval Filmus

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4570

 Ask a Question

 Download Related Notes/Documents