Inequalities for space-bounded Kolmogorov complexity

Preliminary versions of the paper published in 2020 and in 2021. The final (substantially revised) version appeared in 2022.International audienceThere 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