How do you show that for any c, some strings x and y exist, where
K(xy) > K(x) + K(y) + c?

In other words, show that the upper bound of K(xy) cannot be improved
to K(x) + K(y) + c

Hey there,

You would expect that for all strings x and y:
K(xy) <= K(x) + K(y) + C, for some C.  However, this is not true.  

The problem lies in the seperation of d(x) and d(y),  Instead we have
a constanct C such that: K(xy) <= K(x) + K(y) + 2log(K(x)) + C, for
all strings x and y.

Proof:

Let m be the logarithm of |d(x)|, then the string ?1m0 <|d(x)|> d(x)?
gives a self-delimiting description of x.  (We need 2m bits to
indicate the length of d(x).)  Hence the input ?1m0 <|d(x)|> d(x)
d(y)? gives an unambiguous description of xy.

I hope that helps!  

Josh Fraser

sure, but that doesnt prove we can't improve on it, does it?

Just because we can't construct an representation of xy that yields
K(x) + K(y) + c doesn't mean it doesn't exist.

Hello Joshfraz,

Hmm. I never even heard about Kolmogorov complexity before this
question so I won't hesitate to make an answer [unless you ask for
one]. However this certainly sounds like a problem where a proof by
induction would fit the bill.

[1] Based on what you know, can you construct a string x and y such that
  K(xy) > K(x) + K(y) + 1

[2] If yes, and assuming you have a string x and y such that
  K(xy) > K(x) + K(y) + N
can you construct a string xa and yb such that
  K(xayb) > K(xa) + K(yb) + N+1

Based on the comment made by joshfraz, it would seem that extending
the strings x to xa and y to yb by some amount (perhaps the length of
a and b should be based on a function of N) to make the second
relationship true.

Then using induction, you can prove the original statement. If this
works for you, I'd suggest adjusting the list price to a more
appropriate value so I can post a proper answer. If not, perhaps one
of our other researchers can help you.

  --Maniac

I don't think kolmogorov complexity can be computed like that

http://www3.oup.co.uk/computer_journal/hdb/Volume_42/Issue_04/

the high price is because I think this is a difficult problem to solve.

I don't need a well researched, eloquent answer, just a concise proof
that I can understand.