[12] Let n = l(x) and K(x) = n + K(n) + O(1). Show that K(x, n) = K(x) + K(n|x) = K(n) + K(x|n) = K(x, n∗) up to additive constants.

Comments. This relates to the symmetry of information issue for K.

The proof we gave that Theorem 2.8.2 on page 192 is sharp for C does not hold for K. Hence, to obtain that the analogue of Theorem 2.8.2 for K is sharp one has to use another argument. This argument uses the complexity of the complexity function, Theorem 3.7.1, which in fact holds for all variants of Kolmogorov complexity. Source: [P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 1987].