Nonapproximability of the normalized information distance

Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practical application is called ‘normalized compression...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2011-07, Vol.77 (4), p.738-742
Main Authors: Terwijn, Sebastiaan A., Torenvliet, Leen, Vitányi, Paul M.B.
Format: Article
Language:English
Subjects:
Approximation
Classification
Complexity
Compressed
Compressing
Kolmogorov complexity
Normalized information distance
Pattern recognition
Precursors
Semicomputability
Similarity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practical application is called ‘normalized compression distance’ and it is trivially computable. It is a parameter-free similarity measure based on compression, and is used in pattern recognition, data mining, phylogeny, clustering, and classification. The complexity properties of its theoretical precursor, the NID, have been open. We show that the NID is neither upper semicomputable nor lower semicomputable.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2010.06.018