
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)].
Measures of information, entropy, Computer Networks and Communications, Applied Mathematics, Shannon entropy, linear inequalities, Kolmogorov complexity, Ingleton's inequality, Algorithmic information theory (Kolmogorov complexity, etc.), Theoretical Computer Science, Computational Theory and Mathematics
Measures of information, entropy, Computer Networks and Communications, Applied Mathematics, Shannon entropy, linear inequalities, Kolmogorov complexity, Ingleton's inequality, Algorithmic information theory (Kolmogorov complexity, etc.), Theoretical Computer Science, Computational Theory and Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 124 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
