• [34] Show that C and K do not agree, to within any given additive constant, on which strings are more complex. Formally, show that for every positive integer

c, there are strings x, y such that both C(x) − C(y) ≥ c and K(y) − K(x) ≥ c.

Comments. Source: attributed to An.A. Muchnik in [An.A. Muchnik, S.Y. Positselsky, Theor. Comput. Sci., 271:1-2(2002), 15–35]. It follows without too much difficulty from a theorem of [R.M. Solovay Lecture Notes, UCLA, 1975, unpublished] that maximal plain complexity does not imply maximal prefix complexity as in Exercise 3.4.1 on page 221.