Inequalities for Shannon entropy and Kolmogorov complexity (Q1567410): Difference between revisions

It was mentioned by \textit{A. N. Kolmogorov} [IEEE Trans. Inf. Theory IT-14, 662-664 (1968; Zbl 0167.47601)] that the properties of algorithmic complexity and Shannon entropy are similar. We investigate one aspect of this similarity. Namely, we are interested in linear inequalities that are valid for Shannon entropy and for Kolmogorov complexity. It turns out that (1) all linear inequalities that are valid for Kolmogorov complexity are also valid for Shannon entropy and vice versa; (2) all linear inequalities that are valid for Shannon entropy are valid for ranks of finite subsets of linear spaces; (3) the opposite statement is not true, Ingleton's inequality [\textit{A. W. Ingleton}, Combinat. Math. Appl., Proc. Conf. Math. Inst., Oxford 1969, 149-167 (1971; Zbl 0222.05025)] is valid for ranks but not for Shannon entropy; (4) for some special cases, all three classes of inequalities coincide and have a simple description. We present an inequality for Kolmogorov complexity that implies Ingleton's inequality for ranks; another application of this inequality is a new simple proof of one of \textit{P. Gács} and \textit{J. Körner}'s results on common information [Probl. Control Inform. Theory 2, 149-162 (1973; Zbl 0317.94025)].