Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
1  
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
2  
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

1 Answer 1

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.

share|improve this answer
1  
I suppose this raises the obvious question: why not work entirely without the star to begin with? –  Jeremy Kun Nov 17 '12 at 20:19
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.