Proof of an inequality about Kolmogorov complexity of two words.

Question

It is needed to prove an existing of such constant C that for any words $x$,$y$

$K(x,y) \le K(x) + K(y) + log(|x|+|y|) + C$

(K is Kolmogorov complexity)

I tried to prove it by using next true inequalities:

$K(x|l(x)) \le l(x) + c$

and

$K(x) \le K(x|l(x)) + 2log(l(x)) + c$

But theese inequalities are about Kolmogorov complexity for one word and I do not know how to expand them for a case of two words (like in inequality that I must prove). Could you help me please? Thank you in advance.

Answer 1

In fact a stronger statement can be proven:

Since $x$ and $y$ are given, two programs $P_x$ and $P_y$ exist with Kolmogorov complexity $K(x)$ and $K(y)$ to print $x$ and $y$ respectively. We can write another program $P$ without halting the Turing machine as following:

$$P_x \\ P_y$$

This program of length $K(x) + K(y) + C$ prints $x$ and $y$. Hence, in the worst case

$$K(x, y) = K(x) + K(y) + C$$

And in case if you can find a shorter program than $P$ after combining $x$ and $y$, its Kolmogorov complexity will be lesser than above mentioned result. Which means,

$$K(x, y) \le K(x) + K(y) + C$$