$K(xy)\leq K(x)+K(y) +c$?

771 Views Asked by At

Could anyone show that for any $c$, some strings $x$ and $y$ exist, where $K(xy)>K(x)+K(y)+c$? Here $K(x)$ is the Kolmogorov complexity. I already know that $K(xy) \leq 2K(x) + K(y) +c$ and $K(xy) \leq 2\log_2(K(x)) + K(x) + K(y) +c$. But the same ideas of proof cannot be applied to this problem...