Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-026 | 11th April 2000 00:00

Combinatorial Interpretation of Kolmogorov Complexity

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint