Information distance and conditional complexities
C.H. Bennett, P. Gacs, M. Li. P.M.B. Vitanyi, and W.H. Zurek have defined information distance between two strings x, y as d(x, y) = max{K(x/y), K(y/x)}, where K(x/y) is conditional Kolmogorov complexity. It is easy to see that for any string x and any integer n there is a string y such that d(x, y) = n + 0( 1). In this paper we prove the following (stronger) result: for any n and for any string x such that K(x) greater than or equal to 2n + O(1) there exists a string y such that both K(x/y) and K(y/x) are equal to n + O(1). (C) 2002 Elselvier Science B.V. All rights reserved.
information distance kolmogorov conditional complexity