Combinatorial interpretation of Kolmogorov complexity

Kolmogorov's very first paper on algorithmic information theory (Kolmogorov, Problemy peredachi informatsii 1(1) (1965) 3) was entitled "Three approaches to the definition of the quantity of information". These three approaches were called combinatorial, probabilistic and algorithmic. Trying to establish formal connections between combinatorial and algorithmic approaches, we prove that every linear inequality including Kolmogorov complexities could be translated into an equivalent combinatorial statement. (Note that the same linear inequalities are true for Kolmogorov complexity and Shannon entropy, see Hammer et al., (Proceedings of CCC'97, Ulm).) Entropy (complexity) proofs of combinatorial inequalities given in Llewellyn and Radhakrishnan (Personal Communication) and Hammer and Shen (Theory Comput. Syst. 31 (1998) 1) can be considered as special cases (and natural starting points) for this translation. (C) 2002 Published by Elsevier Science B.V.