# Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$

In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \}}{\max \left \{ K(x), K(y) \right \}}$

where $x^*$ is the shortest program outputting $x$. I.e. $K(x) = |x^*|$. In most future papers they drop the star notation, turning the metric into

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y), K(y|x) \right \}}{\max \left \{ K(x), K(y) \right \}}$

I'm unclear on the relationship between the two quantities $K(x|y^*)$ and $K(x|y)$. It seems to me that the former is quite different from the latter, as the latter is providing both $y$ and $K(y)$ as an input to the program computing $x$. However, I can't find any justification as to how these metrics are the same (up to whatever sufficiently sloppy additive precision you like). Could someone point me to an explanation or a reference that clarifies this?

• Perhaps Example 3.9.1 of Li and Vitani book "An introduction to Kolmogorov complexity and its applications" is relevant: $K(x|y) \leq K(x|y^*) + c_{K(\cdot|y^*)}$ ... but it is far beyond my knowledge :) – Marzio De Biasi Nov 17 '12 at 0:05
• I mean this inequality is clear: there is a fixed program which will simulate $y^*$ and output $y$, which can then be used as the auxiliary input to whatever program produces $x$ from $y$. My point is that this inequality should change the nature of the metric. In particular, the theorems proved give inequalities up to $O(1/K)$ additive precision where $K = \max{K(x), K(y)}$. But this is in general smaller than constant additive precision. – Jeremy Kun Nov 17 '12 at 5:15
• the two conditional complexities are indeed different: exists $n$ for which $K(K(x)|x) \geq \log n + 2 \log \log n + O(1)$, but $K(K(x)|x^*) = O(1)$. I didn't read the proofs of the theorems in the paper, do they hold for both conditional complexities ($K(\cdot|x^*)$ and $K(\cdot|x)$)? – Marzio De Biasi Nov 17 '12 at 10:42

As per the comment, $K(x|y) \leq K(x|y^*) + O(1)$. Now denoting the first metric (with the *) by $d_1$ and the second by $d_2$, we have
\displaystyle \begin{align*} d_2(x,y) &= \frac{\max \left \{ K(x|y), K(y|x) \right \} }{\max \left \{ K(x), K(y) \right \}} \\ &\leq \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \} + O(1) }{\max \left \{ K(x), K(y) \right \}} \\ &= d_1(x,y) + O(1/K) \end{align*}
where $K = \max \left \{ K(x), K(y) \right \}$
All of the theorems in the paper give the metric inequalities and universality claims up to an additive factor of $O(1/K)$, so this fits.
• Actually now I'm not so sure. Since the "constant" $O(1)$ depends on $K(y^*)$, it won't be the case that $K(y^*)/K(y) = O(1/K(y))$. If $y^*$ is incompressible, this would be $O(1)$. – Jeremy Kun Dec 1 '12 at 1:31