TR04-031 Authors: Troy Lee, Andrei Romashchenko

Publication: 9th April 2004 21:19

Downloads: 1272

Keywords:

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 additive term $O(\log \C(x,y))$. We are interested in if this property can hold for several versions of polynomial time bounded Kolmogorov complexity.

It is proven in papers by L. Longpr\'e and S. Mocas

and L. Longpr\'e and O. Watanabe that, under a natural assumption, symmetry of information does not hold for the polynomial time bounded printing version of Kolmogorov complexity. In this paper, we investigate symmetry of information for some variants of distinguishing complexity $\CD$, where $\CD(x)$ is the length of a shortest program which accepts $x$ and only $x$. We show relativized worlds where symmetry of information does not hold for deterministic and nondeterministic polynomial time distinguishing complexities $\CD^{\poly}$ and $\CND^{\poly}$. For nondeterministic polynomial time distinguishing with randomness, $\CAM^{\poly}$, we prove that symmetry of information holds for most pairs of strings in any set in $\NP$. In proving this last statement we extend a recent result of Buhrman et al., which may be of independent utility.