Nonapproximability of the normalized information distance

DOI10.1016/j.jcss.2010.06.018zbMath1215.68116OpenAlexW2099666487WikidataQ60362747 ScholiaQ60362747MaRDI QIDQ716306

Paul M. B. Vitányi, Leen Torenvliet, Sebastiaan A. Terwijn

Publication date: 28 April 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/19043

zbMATH Keywords

Kolmogorov complexitynormalized information distancesemicomputability

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

The Normalized Algorithmic Information Distance Can Not Be Approximated ⋮ Similarity and denoising ⋮ Compression-based distance between string data and its application to literary work classification based on authorship ⋮ Normalized information distance and the oscillation hierarchy

Cites Work

• Unnamed Item
• Notes on sum-tests and independence tests
• Systems of strings with high mutual complexity
• Clustering by Compression
• The Similarity Metric
• Information distance
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• An introduction to Kolmogorov complexity and its applications
• Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)
• Logical operations and Kolmogorov complexity
• Independent minimum length programs to translate between given strings
• Information distance and conditional complexities