Combinatorial interpretation of Kolmogorov complexityстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 31 октября 2014 г.
Аннотация: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.