Inequalities for space-bounded Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Pré-Publication, Document De Travail Année : 2020

Inequalities for space-bounded Kolmogorov complexity

Peter Gács
Andrei Romashchenko
Alexander Shen

Résumé

There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples of random variables and Kolmogorov complexities of tuples of strings (Hammer et al., 1997), as well as for sizes of subgroups and projections of sets (Chan, Yeung, Romashchenko, Shen, Vereshchagin, 1998-2002). This parallelism started with the Kolmogorov-Levin formula (1968) for the complexity of pairs of strings with logarithmic precision. Longpré (1986) proved a version of this formula for space-bounded complexities. In this paper we prove an improved version of Longpré's result with a tighter space bound, using Sipser's trick (1980). Then, using this space bound, we show that every linear inequality that is true for complexities or entropies, is also true for space-bounded Kolmogorov complexities with a polynomial space overhead. * Authors want to thank the members of the ESCAPE team (especially Ruslan Ishkuvatov for the help with the proof of Lemma 1), participants of the Kolmogorov seminar (Moscow) and Algorithmic Randomness workshop for discussions.
Fichier principal
Vignette du fichier
2010.10221.pdf (158.08 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03059686 , version 1 (12-12-2020)
lirmm-03059686 , version 2 (17-10-2023)

Identifiants

Citer

Peter Gács, Andrei Romashchenko, Alexander Shen. Inequalities for space-bounded Kolmogorov complexity. 2020. ⟨lirmm-03059686v1⟩
209 Consultations
103 Téléchargements

Altmetric

Partager

More