Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Inequalities for space-bounded Kolmogorov complexity

Peter Gács 1 Andrei Romashchenko 2 Alexander Shen 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata
Contributor : Alexander Shen Connect in order to contact the contributor
Submitted on : Friday, October 8, 2021 - 1:30:42 PM
Last modification on : Friday, October 22, 2021 - 3:07:36 PM


Files produced by the author(s)


  • HAL Id : lirmm-03059686, version 2
  • ARXIV : 2010.10221



Peter Gács, Andrei Romashchenko, Alexander Shen. Inequalities for space-bounded Kolmogorov complexity. 2021. ⟨lirmm-03059686v2⟩



Record views


Files downloads