文章基本信息

标题：Information Distance Revisited
本地全文：下载
作者：Bruno Bauwens
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：46:1-46:14
DOI：10.4230/LIPIcs.STACS.2020.46
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the notion of information distance between two objects x and y introduced by Bennett, GÃ¡cs, Li, Vitanyi, and Zurek [C. H. Bennett et al., 1998] as the minimal length of a program that computes x from y as well as computing y from x, and study different versions of this notion. In the above paper, it was shown that the prefix version of information distance equals max (K(x y),K(y x)) up to additive logarithmic terms. It was claimed by Mahmud [Mahmud, 2009] that this equality holds up to additive O(1)-precision. We show that this claim is false, but does hold if the distance is at least logarithmic. This implies that the original definition provides a metric on strings that are at superlogarithmically separated.
关键词：Kolmogorov complexity; algorithmic information distance