Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-016 | 29th February 2000 00:00

Information Distance and Conditional Complexities

RSS-Feed




TR00-016
Authors: Mikhail V. Vyugin
Publication: 6th March 2000 16:26
Downloads: 1303
Keywords: 


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)$.



ISSN 1433-8092 | Imprint