ECCC-Report TR00-016https://eccc.weizmann.ac.il/report/2000/016Comments and Revisions published for TR00-016en-usMon, 06 Mar 2000 16:26:24 +0200
Paper TR00-016
| Information Distance and Conditional Complexities |
Mikhail V. Vyugin
https://eccc.weizmann.ac.il/report/2000/016C.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)$.
Mon, 06 Mar 2000 16:26:24 +0200https://eccc.weizmann.ac.il/report/2000/016