Nonapproximablity of the Normalized Information Distance

Details Nonapproximablity of the Normalized Information Distance Nonapproximablity of the Normalized Information Distance

2009-10-22

arxiv.org/abs/0910.4353v2

Computer Science

Computational Complexity

LaTeX 8 pages, Submitted. 2nd version corrected some typos

Scientific paper

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 up to any reasonable precision.

Affiliated with

Also associated with

No associations

Rating

Nonapproximablity of the Normalized Information Distance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nonapproximablity of the Normalized Information Distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonapproximablity of the Normalized Information Distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-691164