文章基本信息

标题：Combinatorial Interpretation of Kolmogorov Complexity
本地全文：下载
作者：Andrei Romashchenko ; Alexander Shen ; Nikolai K. Vereshchagin 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The very first Kolmogorov's paper on algorithmic information theory 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 any linear inequality involving Kolmogorov complexities could be translated into an equivalent combinatorial statement.
关键词：algorithmic information theory, combinatorial inequalities, Kolmogorov complexity