<< 1 >>
Rating: 
Summary: Comprehensive and Excellent
Review: Li and Vitanyi have done an admirable job at clarifying some very subtle and deep issues in computational complexity. The organization is clear and natural, and the notation good. While a superb undergraduate might learn from it, I suspect the greatest benefits are to advanced students and practicing professionals.
Rating:
Summary: Careful and clear introduction to a subtle and deep field
Review: Li and Vitanyi have done an admirable job at clarifying some very subtle and deep issues in computational complexity. The organization is clear and natural, and the notation good. While a superb undergraduate might learn from it, I suspect the greatest benefits are to advanced students and practicing professionals.
Rating:
Summary: A must
Review: The book provides all the tools needed for a productive use of the theory. Written by leading experts in the field, the book is both a fascinating introduction as well as a comprehensive reference for experts. The authors are careful to place the development of the theory in its historical context, give a face to the main players in the field and explore frictions with other lines of thought. But the main storyline is the mathematical world of Kolmogorov complexity. Neccessary background knowledge is provided, most proofs are given and the open problems are presented. Most chapters are more or less self sufficient, making it possible to skip those that are of less relevance to you. In the later chapters much thought is given to the different fields of application. A third edition is in the making which will include recent advances. But since the authors make new discoveries available on the web, the present edition will continue for a long time to hold a prominent place in the book shelves of many computer scientist.
Rating:
Summary: The only one of its kind....
Review: The theory of Kolmogorov complexity attempts to define randomness in terms of the complexity of the program used to compute it. The authors give an excellent overview of this theory, and even discuss some of its philosophical ramifications, but they are always careful to distinguish between mathematical rigor and philosophical speculation. And, interestingly, the authors choose to discuss information theory in physics and the somewhat radical idea of reversible computation. The theory of Kolmogorov complexity is slowly making its way into applications, these being coding theory and computational intelligence, and network performance optimization, and this book serves as a fine reference for those readers interested in these applications. Some of the main points of the book I found interesting include: 1. A very condensed but effective discussion of Turing machines and effective computability. 2. The historical motivation for defining randomness and its defintiion using Kolmogorov complexity. 3. The discussion of coding theory and its relation to information theory. The Shannon-Fano code is discussed, along with prefix codes, Kraft's inequality, the noiseless coding theorem, and universal codes for infinite source word sets. 4. The treatment of algorithmic complexity. The authors stress that the information content of an object must be intrinsic and independent of the means of description. 5. The discussion of the explicit universal randomness test. 6. The discussion (in an exercise) of whether a probabilistic machine can perform a task that is impossible on a deterministic machine. 7. The notion of incompressibility of strings. 8. The discussion of randomness in the Diophantine equations; it is shown that the set of indices of the Diophantine equations with infinitely many different solutions is not recursively enumerable; with the initial segment of length n in the characteristic sequence having Kolmogorov complexity n. 9. The discussion on algorithmic probability, especially the test for randomness by martingales. 10. The Solomonoff theory of prediction and its ability to solve the problem of induction. 11. The treatment of Pac-learning and the resultant formalization of Occam's razor. 12. The discussion of compact routing; the optimal space to represent routing schemes in communication networks on the average for all static networks. 13. Computational complexity and its connection to resource-bounded complexity. 14. The notion of logical depth, i.e. the time required by a universal computer to compute the object from its compressed original description. 15. The connection between algorithmic complexity and Shannon's entropy. 16. The discussion on reversible computation, i.e. logically reversible computers that do not dissipate heat. 17. The treatment of information distance, i.e. for two strings, the minimal quantity of information sufficient to translate from one to the other.
Rating:
Summary: The only one of its kind....
Review: The theory of Kolmogorov complexity attempts to define randomness in terms of the complexity of the program used to compute it. The authors give an excellent overview of this theory, and even discuss some of its philosophical ramifications, but they are always careful to distinguish between mathematical rigor and philosophical speculation. And, interestingly, the authors choose to discuss information theory in physics and the somewhat radical idea of reversible computation. The theory of Kolmogorov complexity is slowly making its way into applications, these being coding theory and computational intelligence, and network performance optimization, and this book serves as a fine reference for those readers interested in these applications. Some of the main points of the book I found interesting include: 1. A very condensed but effective discussion of Turing machines and effective computability. 2. The historical motivation for defining randomness and its defintiion using Kolmogorov complexity. 3. The discussion of coding theory and its relation to information theory. The Shannon-Fano code is discussed, along with prefix codes, Kraft's inequality, the noiseless coding theorem, and universal codes for infinite source word sets. 4. The treatment of algorithmic complexity. The authors stress that the information content of an object must be intrinsic and independent of the means of description. 5. The discussion of the explicit universal randomness test. 6. The discussion (in an exercise) of whether a probabilistic machine can perform a task that is impossible on a deterministic machine. 7. The notion of incompressibility of strings. 8. The discussion of randomness in the Diophantine equations; it is shown that the set of indices of the Diophantine equations with infinitely many different solutions is not recursively enumerable; with the initial segment of length n in the characteristic sequence having Kolmogorov complexity n. 9. The discussion on algorithmic probability, especially the test for randomness by martingales. 10. The Solomonoff theory of prediction and its ability to solve the problem of induction. 11. The treatment of Pac-learning and the resultant formalization of Occam's razor. 12. The discussion of compact routing; the optimal space to represent routing schemes in communication networks on the average for all static networks. 13. Computational complexity and its connection to resource-bounded complexity. 14. The notion of logical depth, i.e. the time required by a universal computer to compute the object from its compressed original description. 15. The connection between algorithmic complexity and Shannon's entropy. 16. The discussion on reversible computation, i.e. logically reversible computers that do not dissipate heat. 17. The treatment of information distance, i.e. for two strings, the minimal quantity of information sufficient to translate from one to the other.
Rating:
Summary: Comprehensive and Excellent
Review: This is one of the best-written mathematical texts I've read. It builds up the theory from basic principles, and illustrates it with numerous examples and applications. A definitive work.
Rating:
Summary: Excellent if you have the math...
Review: to understand it. This book is intended for serious students of computer science or those who have some similar training - it is definitely set up as a textbook. However, that being said, if you have the background the authors' delivery is fist-class and very clear. The reviews below give more than enough information so I won't belabour the Kolmogorov complexity here. Suffice it to say you won't find the subject detailed more fully in any other reference work in existence today. However, this book does need to be revised and updated. There has been a lot of development in the field and the sections overviewing Solomonoff's work, in particular, could be expanded. Also, I found it hard to believe that nothing about the 'philosophical' importance of the whole induction question - this is at the core of many very important questions and should not be treated trivially. There should also be some overview of two other areas that, in combination with the theory outlined in this text, are starting to form the nexus of a "new kind of science" (definitely not Wolfram's pathetic attempt). I refer to some information regarding non-classical logical systems as well as anticipatory computing systems. Both will, I predict, become core areas in addition to extensions to Kolmogorov/Chaitin complexity in the future. All textbooks should be as clear and concise as this example.
Rating:
Summary: Excellent if you have the math...
Review: to understand it. This book is intended for serious students of computer science or those who have some similar training - it is definitely set up as a textbook. However, that being said, if you have the background the authors' delivery is fist-class and very clear. The reviews below give more than enough information so I won't belabour the Kolmogorov complexity here. Suffice it to say you won't find the subject detailed more fully in any other reference work in existence today. However, this book does need to be revised and updated. There has been a lot of development in the field and the sections overviewing Solomonoff's work, in particular, could be expanded. Also, I found it hard to believe that nothing about the 'philosophical' importance of the whole induction question - this is at the core of many very important questions and should not be treated trivially. There should also be some overview of two other areas that, in combination with the theory outlined in this text, are starting to form the nexus of a "new kind of science" (definitely not Wolfram's pathetic attempt). I refer to some information regarding non-classical logical systems as well as anticipatory computing systems. Both will, I predict, become core areas in addition to extensions to Kolmogorov/Chaitin complexity in the future. All textbooks should be as clear and concise as this example.
Rating:
Summary: THE book on Kolmogorov Complexity
Review: When is an object "random"? Kolmogorov (and others) argue that one could measure randomness by the shortest description, i.e. computer program, that generates it. This simple idea leads to a beautiful mathematical theory and a powerful tool as one can show that random objects have several interesting properties. Li and Vitanyi have written this wonderful monograph on the area covering the depth of theory and applications not seen anywhere else. They give a clear and complete descriptions of many of the important concepts in the book. I have used this book twice in teaching graduate courses on the topic. This book is a must have for anyone interested in a serious mathematical treatment of Kolmogorov complexity.
Rating:
Summary: THE book on Kolmogorov Complexity
Review: When is an object "random"? Kolmogorov (and others) argue that one could measure randomness by the shortest description, i.e. computer program, that generates it. This simple idea leads to a beautiful mathematical theory and a powerful tool as one can show that random objects have several interesting properties. Li and Vitanyi have written this wonderful monograph on the area covering the depth of theory and applications not seen anywhere else. They give a clear and complete descriptions of many of the important concepts in the book. I have used this book twice in teaching graduate courses on the topic. This book is a must have for anyone interested in a serious mathematical treatment of Kolmogorov complexity.
<< 1 >>
| 
