3
$\begingroup$

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

$\endgroup$
  • $\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 '19 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$ – Yuval Filmus Nov 24 '19 at 7:13
6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.