Normalized Information Distance and the Oscillation Hierarchy

August 11, 2017 · The Ethereal · 🏛 Journal of computer and system sciences (Print)

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn arXiv ID 1708.03583 Category math.LO: Logic Cross-listed cs.CC, cs.IT Citations 1 Venue Journal of computer and system sciences (Print) Last Checked 1 month ago
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Logic