2026-07-24T05:02:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11907 2024-03-06T10:48:59Z ddc:004 open_access

Information Distance Revisited Bauwens, Bruno Kolmogorov complexity algorithmic information distance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruno Bauwens 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.46 urn:nbn:de:0030-drops-119071 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.46 eng https://creativecommons.org/licenses/by/3.0/legalcode