Inequalities for space-bounded Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Preprints, Working Papers, ... Year : 2020

Inequalities for space-bounded Kolmogorov complexity

Peter Gács
Andrei Romashchenko
Alexander Shen

Abstract

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
Origin Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

Peter Gács, Andrei Romashchenko, Alexander Shen. Inequalities for space-bounded Kolmogorov complexity. 2020. ⟨lirmm-03059686v1⟩
192 View
87 Download

Altmetric

Share

More