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-035 | 6th June 2000 00:00

Independent minimum length programs to translate between given strings

RSS-Feed




TR00-035
Authors: Nikolay Vereshchagin, Mikhail V. Vyugin
Publication: 6th June 2000 18:21
Downloads: 926
Keywords: 


Abstract:

A string $p$ is called a program to compute $y$ given $x$
if $U(p,x)=y$, where $U$ denotes universal programming language.
Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$
is defined as minimum length of
a program to compute $y$ given $x$.
Let $K(x)$ denote $K(x|\text{empty string})$
(Kolmogorov complexity of $x$) and
let $I(x:y)=K(x)+K(y)-K(\pair{x,y})$
(the amount of mutual information in $x,y$).
In the present paper we answer in negative the following
question posed in~\cite{id}:
Is it true that for any
strings $x,y$ there are
independent minimum length programs $p,q$ to translate between $x,y$,
that is, is it true that
for any $x,y$ there are $p,q$ such that $U(p,x)=y$, $U(q,y)=x$,
the length of $p$ is $K(y|x)$,
the length of $q$ is $K(x|y)$, and
$I(p:q)=0$ (where the last three equalities hold up
to an additive $O(\log(K(x|y)+K(y|x)))$ term)?



ISSN 1433-8092 | Imprint