__
TR00-016 | 29th February 2000 00:00
__

#### Information Distance and Conditional Complexities

**Abstract:**
C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, 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 the 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+O(1)$.

In this paper we prove the following (stronger) result: for any

$n$ and for any string $x$ such that $K(x)\ge 3n+O(1)$ there

exists a string $y$ such that both $K(x|y)$ and $K(y|x)$ are

equal to $n+O(1)$.