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?
Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$
it.information theory;kolmogorov complexity