Portal de Periódicos da CAPES

Combinatorial interpretation of Kolmogorov complexity

2002; Elsevier BV; Volume: 271; Issue: 1-2 Linguagem: Inglês

10.1016/s0304-3975(01)00034-2

1879-2294

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin,

semigroups and automata theory

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.