• [17] Let k be a positive integer, X a multiset of strings with d(X) ≥ 2, and maxx∈X{K(X|x)} = k. Information distance in a multiset of strings using plain Kolmogorov complexity is defined in Definition 8.5.1 on page 698. Originally it was defined as ID(X) = min{l(p) :

U(p,x, d(X) ) = X for all x ∈ X} where U is the reference universal prefix Turing machine. Show that ID(X) ≤ k + O(log k).

Comments. Source: Theorem 3.1 in [P.M.B. Vit´anyi, IEEE Trans. Inform. Theory, 57:4(2011), 2451–2456]. Hint: the proof in the source also proves maximum overlap (as in Section 8.3.2 on page 664). Without proving maximum overlap it is simpler to prove the asked result using the method used in Theorem 8.5.1 adapted for prefix complexities. The result is related to Theorem 2 in [C. Long, X. Zhu, M. Li, and B. Ma, Proc. 17th ACM Conf. Inform. Knowledge Management, 2008, 1213–

1220]. The proof given there assumes essentially that the difference of two prefix complexities is computable. This is not the case. The proof also violates Exercise 8.3.15 on page 683