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?
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) &amp;= \frac{\max \left \{ K(x|y), K(y|x) \right \} }{\max \left \{ K(x), K(y) \right \}} \\ &amp;\leq \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \} + O(1) }{\max \left \{ K(x), K(y) \right \}} \\ &amp;= 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.