Title: Normalized Information Distance and the Oscillation Hierarchy,
Abstract: We study the complexity of approximations to the normalized information
distance. We introduce a hierarchy of computable approximations by considering
the number of oscillations. This is a function version of the difference
hierarchy for sets. We show that the normalized information distance is not in
any level of this hierarchy, strengthening previous nonapproximability results.
As an ingredient to the proof, we also prove a conditional undecidability
result about independence.