An introduction to Kolmogorov complexity and its applications. 2nd ed. (English) Zbl 0866.68051

Graduate Texts in Computer Science. New York, NY: Springer. xx, 637 p. (1997).
[For the review of the first ed. (Springer 1993) see Zbl 0805.68063.]
When this book was conceived ten years ago, few scientists realized the width of scope and the power for applicability of the central ideas. Partially because of the enthusiastic reception of the first edition, open problems have been solved and new applications have been developed.
We have added new material on the relation between data compression and minimum description length induction, computational learning, and universal prediction; circuit theory ; distributed algorithmics; instance complexity; CD compression; computational complexity; Kolmogorov random graphs; shortest encoding of routing tables in communication networks; computable universal distributions; average case properties; the equality of statistical entropy and expected Kolmogorov complexity; and so on. Apart from being used by researchers and as reference work, the book is now commonly used for graduate courses and seminars.
In recognition of this fact, the second edition has been produced in textbook style. We have preserved as much as possible the ordering of the material as it was in the first edition. The many exercises bunched together at the ends of some chapters have been moved to the appropriate sections. The comprehensive bibliography on Kolmogorov complexity at the end of the book has been updated, as have the “History and References” sections of the chapters.


68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
60A05 Axioms; other general questions in probability
03B48 Probability and inductive logic
82B03 Foundations of equilibrium statistical mechanics
94A17 Measures of information, entropy


Zbl 0805.68063