The Kolmogorov complexity of an object is how briefly it can be described. It has applications in programming, artificial intelligence, information theory, statistics, and related fields. Chapters discuss algorithmic complexity, algorithmic prefix complexity, algorithmic probability, inductive reasoning, the incompressibility method, resource-bounded complexity, and physics and computation. Exercises are included and are graded from simple problems that can be answered off the top of the head, to research problems. Annotation copyright Book News, Inc. Portland, Or.
