Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Denote by $y^*$ the shortest program computing the string $y$. In the main textbook and various papers of Li & Vitanyi, I have seen the following statements.

The first is well established: the symmetry of information

$K(x,y) = K(y) + K(x|y^*) = K(x) + K(y|x^*)$ (up to additive constants)

I have also seen them drop the $y^*$ and assert that this equality is still true up to additive constant precision (say, in the paper "The Similarity Metric" (bottom of page 8, first column)). On the other hand, I have only been able to prove that

$K(x|y^*) \leq K(x|y) + O(1)$, and

$K(x|y) \leq K(x|y^*) + O(\log(K(y)))$

And it appears that the latter is not true if we replace the logarithm with a constant. For instance, $K(K(x)|x)$ is ostensibly logarithmic in size (since $K$ is uncomputable), but $K(K(x)|x^*)$ is easily seen to be a constant.

My question is, how can they assert that $K(x|y) = K(x,y)-K(y)$ without having $K(x|y^*) = K(x|y)$ up to an additive constant?

share|cite|improve this question
After a while it appears to me that this is either a typo or intentional sloppiness to emphasize the fact that these are approximations in practice. Oh well. – JeremyKun Dec 21 '12 at 1:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.