An Introduction to Kolmogorov Complexity and Its Applications (original) (raw)

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 <align="right"> Quick-Click Buying from Amazon (often with a rebate):

</align="right">

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:

• Pointwise Randomness. Kolmogorov complexity is a modern notion of randomness dealing with the quantity of information in individual objects; that is, pointwise randomness rather than average randomness as produced by a random source. It was proposed by A.N. Kolmogorovin 1965 to quantify the randomness of individual objects in an objective and absolute manner. This is impossible by classical probability theory (a branch of measure theory satisfying the so-called Kolmogorov axioms formulated in 1933). Kolmogorov complexity is known variously as `algorithmic information', `algorithmic entropy', `Kolmogorov-Chaitin complexity', `descriptional complexity', `shortest program length', `algorithmic randomness', and others.
• **Incompressibility Method.**In some parts of the research interests mentioned on Paul Vitanyi's home page a new mathematical proof technique was developed, now known as the `incompressibility method'. The incompressibility method is a basic general technique such as the `pigeon hole' argument, `the counting method' or the `probabilistic method'. The new method is based on Kolmogorov complexity.
• **Absolute Information.**The Kolmogorov complexity of an object is a form of absolute information of the individual object. This is not possible to do by C.E. Shannon's information theory. Unlike Kolmogorov complexity, information theory is only concerned with the average information of a random source.
• **Universal Induction and Data Compression.**Traditional wisdom has it that the better a theory compresses the learning data concerning some phenomenon under investigation, the better we learn, generalize, and the better the theory predicts unknown data. This belief is vindicated in practice but before the advent of Kolmogorov complexity has not been rigorously proved in a general setting. Making these ideas rigorous involves the length of the shortest effective description of an individual object: its Kolmogorov complexity.Ray Solomonoff invented the notion of universal prediction using the Kolmogorov complexity based universal distribution. Universal prediction is related to optimal effective compression. The latter is almost always a best strategy in hypotheses identification (an ideal form of the minimum description length (MDL) principle). Whereas the single best hypothesis does not necessarily give the best prediction, it can be demonstrated that nonetheless compression is almost always the best strategy in prediction methods in the style of R. Solomonoff. Ashort biography of Kolmogorov is available. `Kolmogorov' complexity was earlier proposed by Ray Solomonoffin a Zator Technical Report in 1960 and in a long paper in Information and Control in 1964. Also Gregory Chaitinproposed 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
• randomness of individual finite objects or infinite sequences, Martin-Loef tests for randomness, Goedel's incompleteness result, information theory of individual objects,
• universal probability, general inductive reasoning, inductive inference, prediction, mistake bounds, computational learning theory, inference in statistics,
• the incompressibility method, combinatorics, graph theory, Kolmogorov 0-1 Laws, probability theory,
• theory of parallel and distributed computation, time and space complexity of computations, average case analysis of algorithms such as HEAPSORT, language recognition, string matching, routing in computer networks, circuit theory, formal language and automata theory, parallel computation, Turing machine complexity, complexity of tapes, stacks, queues, average complexity, lower bound proof techniques,
• structural complexity theory, oracles,
• logical depth, universal optimal search, physics and computation, dissipationless reversible computing, information distance and picture similarity, thermodynamics of computing, statistical thermodynamics and Boltzmann entropy.

A comprehensive as well as introductory treatment is given in the (text)bookMing 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 andContents 2nd Edition.

Click here for thean utterly simple computation modelfor ``hands-on'' experience with concrete Kolmogorov complexity.

See also some of ourpapers on Kolmogorov Complexity and Its Applications.
This page is maintained byPaul Vitanyi, at CWIand was last modified a short while ago.