{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:41:28Z","timestamp":1759146088591,"version":"3.44.0"},"reference-count":16,"publisher":"SAGE Publications","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2022,12,21]]},"abstract":"<jats:p>Finding all linear inequalities for entropies remains an important open question in information theory. For a long time the only known inequalities for entropies of tuples of random variables were Shannon (submodularity) inequalities. Only in 1998 Zhang and Yeung\u00a01998 found the first inequality that cannot be represented as a convex combination of Shannon inequalities, and several other non-Shannon inequalities were found soon after that. It turned out that the class of linear inequalities for entropies is rather fundamental, since the same class can be equivalently defined in terms of subgroup sizes or projections of multidimensional sets (Chan\u00a02001, Chan, Yeung\u00a02002, Romashchenko, Shen, Vereshchagin\u00a02000). The non-Shannon inequalities have interesting applications (e.g., to proofs of lower bounds for the information ratio of secret sharing schemes). Still the class of linear inequalities for entropies is not well understood, though some partial results are known (e.g., Mat\u00fa\u0161 has shown in 2007 that this class cannot be generated by a finite family of inequalities). This class also appears in algorithmic information theory: 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). This parallelism started with the Kolmogorov\u2013Levin formula\u00a01968 for the complexity of pairs of strings with logarithmic precision. Longpr\u00e9 proved in 1986 a version of this formula for the space-bounded complexities. In this paper we prove a stronger version of Longpr\u00e9\u2019s result with a tighter space bound, using Sipser\u2019s trick\u00a01980. Then, using this result, 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, thus extending the parallelism to the space-bounded algorithmic information theory.<\/jats:p>","DOI":"10.3233\/com-210374","type":"journal-article","created":{"date-parts":[[2022,9,9]],"date-time":"2022-09-09T13:52:54Z","timestamp":1662731574000},"page":"165-185","source":"Crossref","is-referenced-by-count":2,"title":["Inequalities for space-bounded Kolmogorov complexity"],"prefix":"10.1177","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6138-0591","authenticated-orcid":false,"given":"Bruno","family":"Bauwens","sequence":"first","affiliation":[{"name":"National Research University Higher School of Economics, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2496-0332","authenticated-orcid":false,"given":"Peter","family":"G\u00e1cs","sequence":"additional","affiliation":[{"name":"Boston University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7723-7880","authenticated-orcid":false,"given":"Andrei","family":"Romashchenko","sequence":"additional","affiliation":[{"name":"LIRMM, University of Montpellier, CNRS, Montpellier, France and IITP RAS, Moscow (on leave)"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8605-7734","authenticated-orcid":false,"given":"Alexander","family":"Shen","sequence":"additional","affiliation":[{"name":"LIRMM, University of Montpellier, CNRS, Montpellier, France and IITP RAS, Moscow (on leave)"}]}],"member":"179","reference":[{"key":"10.3233\/COM-210374_ref1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1247066.1247068","article-title":"Computational complexity and G\u00f6del\u2019s incompleteness theorem","volume":"9","author":"Chaitin","year":"1971","journal-title":"SIGACT News"},{"issue":"3","key":"10.3233\/COM-210374_ref2","doi-asserted-by":"publisher","first-page":"241","DOI":"10.4310\/CIS.2001.v1.n3.a1","article-title":"A combinatorial approach to information inequalities","volume":"1","author":"Chan","year":"2001","journal-title":"Communications in Informations and Systems"},{"issue":"7","key":"10.3233\/COM-210374_ref3","doi-asserted-by":"crossref","first-page":"1992","DOI":"10.1109\/TIT.2002.1013138","article-title":"On a relation between information inequalities and group theory","volume":"IT-48","author":"Chan","year":"2002","journal-title":"IEEE Transactions on Information Theory"},{"key":"10.3233\/COM-210374_ref5","doi-asserted-by":"crossref","unstructured":"D.\u00a0Hammer, A.\u00a0Romashchenko, A.\u00a0Shen and N.\u00a0Vereshchagin, Inequalities for Shannon entropies and Kolmogorov complexities, in: Proceedings 12th IEEE Conference on Computational Complexity, Journal of Computer and System Sciences, Ulm, 1997, pp.\u00a013\u201323, Final version: Journal of Computer and System Sciences 60, 442\u2013464..","DOI":"10.1006\/jcss.1999.1677"},{"key":"10.3233\/COM-210374_ref6","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Problems of Information Transmission"},{"key":"10.3233\/COM-210374_ref7","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1109\/TIT.1968.1054210","article-title":"Logical basis for information theory and probability theory","volume":"14","author":"Kolmogorov","year":"1968","journal-title":"IEEE Transaction on Information Theory"},{"issue":"2","key":"10.3233\/COM-210374_ref9","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(93)90204-M","article-title":"Symmetry of information and one-way functions","volume":"46","author":"Longpr\u00e9","year":"1993","journal-title":"Information processing letters"},{"key":"10.3233\/COM-210374_ref10","doi-asserted-by":"crossref","unstructured":"F.\u00a0Mat\u00fa\u0161, Infinitely many information inequalities, in: Proc. IEEE International Symposium on Information Theory, 2007, pp.\u00a041\u201344.","DOI":"10.1109\/ISIT.2007.4557201"},{"key":"10.3233\/COM-210374_ref11","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s00224-012-9432-1","article-title":"Improving the space-bounded version of Muchnik\u2019s conditional complexity theory via naive derandomization","volume":"55","author":"Musatov","year":"2014","journal-title":"Theory of Computing Systems"},{"key":"10.3233\/COM-210374_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2000.856743"},{"key":"10.3233\/COM-210374_ref13","doi-asserted-by":"crossref","unstructured":"A.\u00a0Shen, Algorithms and Programming: Problems and Solutions, 2nd edn, Springer, 2010.","DOI":"10.1007\/978-1-4419-1748-5"},{"key":"10.3233\/COM-210374_ref14","doi-asserted-by":"crossref","unstructured":"A.\u00a0Shen, V.A.\u00a0Uspensky and N.\u00a0Vereshchagin, Kolmogorov Complexity and Algorithmic Randomness, AMS, 2018.","DOI":"10.1090\/surv\/220"},{"key":"10.3233\/COM-210374_ref15","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","article-title":"Halting space-bounded computations","volume":"10","author":"Sipser","year":"1980","journal-title":"Theoretical Computer Science"},{"key":"10.3233\/COM-210374_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21852-6_17"},{"key":"10.3233\/COM-210374_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50062-1_41"},{"issue":"4","key":"10.3233\/COM-210374_ref18","doi-asserted-by":"publisher","first-page":"1440","DOI":"10.1109\/18.681320","article-title":"On characterization of entropy function via information inequalities","volume":"IT-44","author":"Zhang","year":"1998","journal-title":"IEEE Transactions in Information Theory"}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-210374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:14Z","timestamp":1757420534000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-210374"}},"subtitle":[],"editor":[{"given":"Vasco","family":"Brattka","sequence":"additional","affiliation":[]},{"given":"Noam","family":"Greenberg","sequence":"additional","affiliation":[]},{"given":"Iskander","family":"Kalimullin","sequence":"additional","affiliation":[]},{"given":"Mariya","family":"Soskova","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,12,21]]},"references-count":16,"journal-issue":{"issue":"3-4"},"URL":"https:\/\/doi.org\/10.3233\/com-210374","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"type":"electronic","value":"2211-3576"},{"type":"print","value":"2211-3568"}],"subject":[],"published":{"date-parts":[[2022,12,21]]}}}