patternMinorCanonical
Kolmogorov Complexity of String Concatenation
Viewed 0 times
concatenationstringcomplexitykolmogorov
Problem
For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) > K(x)$?
Solution
Let $w = 0^{2^n}$, so that $K(w) = O(\log n)$. The string $w$ has $2^n+1$ prefixes, and so some prefix $x$ satisfies $K(x) \geq n$. This example strongly violates your inequality.
On the other hand, given $xy$ and $|x|$, we can easily extract $x$. This shows that $K(x) \leq K(xy) + O(K(|x|))$. In particular, if $|x| = n$ then $K(xy) \geq K(x) - O(\log n)$.
On the other hand, given $xy$ and $|x|$, we can easily extract $x$. This shows that $K(x) \leq K(xy) + O(K(|x|))$. In particular, if $|x| = n$ then $K(xy) \geq K(x) - O(\log n)$.
Context
StackExchange Computer Science Q#117519, answer score: 7
Revisions (0)
No revisions yet.