[42] Let x be a string of length n.

(a) Show that the equality C(x, C(x)) = C(C(x)|x) + C(x) + O(1) can be satisfied only to within an additive term of about log n.

(b) Prove that C(x, y) = C(x|y) + C(y) can hold only to within an additive logarithmic term without using Exercise 2.8.1, Item (a), and Exercise 2.8.6.

(c) Show that C(x) = C(x|C(x)) + O(1).

(d) Show that C(C(x)|x) ≤ log n + O(1).

Comments. Hint for Item (a): use Exercise 2.8.1, Item (a), and Exercise 2.8.6.

Hint for Item (b): additivity is already violated on random strings of random length. Hint for Item (c): suppose that x can be described by q with condition C(x) which is shorter than C(x). Then we can describe x by q plus C(x) − l(q) bits and we obtain a description of x shorter than C(x): contradiction. Hint for Item (d): see the first paragraphs of Section 3.7. Source: [P. G´acs, Ibid.; A.K. Zvonkin and L.A.
Levin, Russ. Math. Surv., 25:6(1970), 83–124].