For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) > K(x)$?

  • $\begingroup$ (Expect any example having a shortish description in natural language or any formalism of choice to have a short program. That said, how about x the binary representation of Ackermann-Péter(4, 2) sans last bit, y 1?) $\endgroup$
    – greybeard
    Nov 24, 2019 at 7:04
  • $\begingroup$ I don’t think that always holds. For example $xy$ could have very low complexity. Of course given $xy$ you could extract $x$ given its length, so your inequality holds with the corresponding error term. $\endgroup$ Nov 24, 2019 at 7:13

2 Answers 2


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


While this example might have to be tweaked a little, consider a bitstring of 8192 zeroes followed by 273 ones. Let's call this string x. Now let's have y equal to 7919 ones.

Now concatenate: The string xy is 2^13 zeroes followed by 2^13 ones. It has a shorter description than x or y, and one can probably write a shorter algorithm to generate it that to generate either x or y alone.

Following an approach like this, for any given constant c, I think one could make an example where K(xy) < K(x) - c and K(xy) < K (y) - c.


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.