Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TREVISAN'S FUNCTION:
Reports tagged with Trevisan's function:
TR04-031 | 22nd March 2004
Troy Lee, Andrei Romashchenko

On Polynomially Time Bounded Symmetry of Information

The information contained in a string $x$ about a string $y$
is defined as the difference between the Kolmogorov complexity
of $y$ and the conditional Kolmogorov complexity of $y$ given $x$,
i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small ... more >>>




ISSN 1433-8092 | Imprint