[39]

(a) Show that for strings x and y that are random with respect to one another in the sense that K(x|y) ≥ l(x) and K(y|x) ≥ l(y),

there are p and q such that K(p) = K(y|x), K(q) = K(x|y), I(p; q) = 0, U(p, x) = y, and U(q, y) = x, where the first three equalities hold up to an additive O(K(x|y) + K(y|x)) term.

(b) Give a proof of Corollary 8.3.3 using the conversion theorem, Theorem 8.3.1.

(c) Show that Muchnik’s theorem, Theorem 8.3.7, does not hold if we replace the additive term O(log C(xy)) by O(log(C(x|y) + C(y|x))).
Comments. Source: Item (a): [C.H. Bennett, P. G´acs, M. Li, P.M.B.
Vit´anyi, and W.H. Zurek, IEEE Trans. Inform. Theory, 44:4(1998), 1407–1423] attributed to N.K. Vereshchagin; Items

(b) and (c): [N.K.
Vereshchagin and M.V. Vyugin, Theoret. Comput. Sci., 271(2002), 131–
143].