An Introduction to Kolmogorov Complexity and Its Applications

Ming Li and Paul Vitanyi

Third Edition 
Springer Verlag
2008; xxiii+790pp
50 Illustrations
ISBN 987-0-387-49820-1
Hardcover $84.95 as of December 2008 (maybe cheaper from Amazon) 

Preface 3nd Edition.

Preface 2nd Edition.

Contents 2nd Edition.

Chinese Translation 

Quick-Click Buying from Amazon (often with a rebate): 

Chinese translation by Cheng Qi: ``Description Complexity and Applications,'' China Science Press, Beijing, December 1998 (1999 National 1st Prize for Excellent Books in Science and Technology published in the Peoples Republic of China.) Translation of parts in Russian by A.K. Shen and N.K. Vereshchagin in ``Uspekhi Mat. Nauk'' and in Japanese by O. Watanabe in ``Handbook of Theoretical Computer Science.''

Achievements of the area: A short biography of Kolmogorov is available. `Kolmogorov' complexity was earlier proposed by Ray Solomonoff in a Zator Technical Report in 1960 and in a long paper in Information and Control in 1964. Also Gregory Chaitin proposed this idea in a paper in J. ACM in 1969. This paper continues a paper by G. Chaitin in J.ACM in 1966, which however was concerned with a complexity measure based on Turing machine state-symbol product following ideas of C.E. Shannon. Unlike Kolmogorov complexity, those complexity measures are not objective and absolute (recursively invariant).
After we and others pioneered several successful applications of Kolmogorov complexity in the theory of computation, the general pattern of the incompressibility method emerged. The incompressibility method and Kolmogorov complexity is truly a versatile mathematical tool. It is a sharper relative of classical information theory (absolute information of individual object rather than average information over a random ensemble) and yet satisfies many of the laws of classical information theory---although with a slight error term. Applications of Kolmogorov complexity by us and others have been given in a plethora of areas, including
A comprehensive as well as introductory treatment is given in the (text)book Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, New York, 1993; Revised and Expanded Second Edition 1997. See Preface 2nd Edition and Contents 2nd Edition.

Click here for the an utterly simple computation model for ``hands-on'' experience with concrete Kolmogorov complexity.
See also some of our papers on Kolmogorov Complexity and Its Applications.
This page is maintained by Paul Vitanyi, at CWI and was last modified a short while ago.