Inequalities for Shannon entropy and Kolmogorov complexity

It was mentioned by Kolmogorov (1968. IEEE Trans. Inform. Theory 14. 662-66 4) that the properties of algorithmic complexity and Shannon entropy are si milar. We investigate one aspect of this similarity. Namely, we are interes ted in linear inequalities that are valid for Shannon entropy and for Kolmo gorov complexity. It turns out that (1) all linear inequalities that are va lid for Kolmogorov complexity are also valid for Shannon entropy and vice v ersa: (2) all linear inequalities that are valid for Shannon entropy are va lid for ranks of finite subsets of linear spaces: (3) the opposite statemen t is not true: Ingleton's inequality (1971, "Combinatorial Mathematics and Its Applications." pp. 149-167. Academic Press, San Diego) is valid for ran ks but not for Shannon entropy; (4) for some special cases all three classe s of inequalities coincide and have simple description. We present an inequ ality for Kolmogorov complexity that implies Ingleton's inequality for rank s; another application of this inequality is a new simple proof of one of G acs-Korner's results on common information (1973. Problems Control Inform. Theory 2, 149-162). (C) 2000 Academic Press.