[38] Show that there are strings

a, b, and p of lengths n, 2n, and k ≥ 2n, respectively, having the following properties: (i) C(b|a, p) =

0; (ii) C(p|a) ≥ k; (iii) there is no string q such that C(q) ≤ k − n, C(q|p) ≤ n, and C(b|a, q) ≤ n, all (in)equalities holding to within an additive term O(log(k + n)).

Comments. Muchnik’s theorem, Theorem 8.3.7, can be interpreted as follows. Given strings x and y, is it possible to find a simplification p of x (which may be regarded as a description of itself) such that C(x|y, p) = 0, l(p) = C(x|y), and C(p|x) = 0, with equality up to an additive O(log C(xy)) term? In general, if we are given a description p of x|y, a simplification of p might not exist even if p is much larger than C(x|y). The exercise formalizes this question. Source: [An.A. Muchnik, A.K. Shen, M.A. Ustinov, N.K. Vereshchagin, and M.V. Vyugin, Proc.

Theory Applications Models Comput., Lect. Notes Comp. Sci., Vol. 3959, Springer-Verlag, 2006, 308–317]. There it is also shown that the above holds for all

a, b, and k except for some trivial cases such as C

(a) = 0.