An Introduction To Kolmogorov Complexity and its Applications
Inhaltsverzeichnis
Reference
Li, M., Vitányi, P.: An Introduction To Kolmogorov Complexity and its Applications. 3nd edn. Springer, New York (2008).
DOI
http://www.springer.com/mathematics/applications/book/978-0-387-33998-6
Abstract
Develops Kolmogorov theory in detail and outlines the wide range of illustrative applications
Presents recent, major results in the field: topics include Omega numbers, Kolmogorov-Loveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, and Shannon information
Introduces results from prominent researchers in the field, such as those found by Slaman-Kucera, Downey, Hirschfeldt, Nies, Solovay, Miller and many more
Includes applications to hierarchical clustering, phylogeny in genomics, classification of music, Google, and the World Wide Web
Additional exercises on new results
Improved sections on high-probability properties and Kolmogorov’s structure function, information distance
This ongoing bestseller, now in its third edition, is considered the standard reference on Kolmogorov complexity, a modern theory of information that is concerned with information in individual objects.
New key features and topics in the 3rd edition:
- New results on randomness
- Kolmogorov's structure function, model selection, and MDL
- Incompressibility method: counting unlabeled graphs, Shellsort, communication complexity
- Derandomization
- Kolmogorov complexity versus Shannon information, rate distortion, lossy compression, denoising
- Theoretical results on information distance
- The similarity metric with applications to genomics, phylogeny, clustering, classification, semantic meaning, question-answer systems
- Quantum Kolmogorov complexity
Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in all fields of science. It is self-contained: it contains the basic requirements from mathematics, probability theory, statistics, information theory, and computer science. Included are history, theory, new developments, a wide range of applications, numerous (new) problem sets, comments, source references, and hints to solutions of problems. This is the only comprehensive treatment of the central ideas of Kolmogorov complexity and their applications.
Extended Abstract
Reviews
Bibtex
Table of contents
Preface to the First Edition . . . . . . . . . . . . . . . . . . . . vii
Preface to the Second Edition . . . . . . . . . . . . . . . . . . xi
Preface to the Third Edition . . . . . . . . . . . . . . . . . . . xii
How to Use This Book . . . . . . . . . . . . . . . . . . . . . . xii
Outlines of One-Semester Courses . . . . . . . . . . . . . . . . xv
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
1 Preliminaries
1.1 A Brief Introduction . . . . . . . . . . . . . . . . . . . . . 1
1.2 Prerequisites and Notation . . . . . . . . . . . . . . . . . 7
1.3 Numbers and Combinatorics . . . . . . . . . . . . . . . . 8
1.4 Binary Strings . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . 15
1.6 Basics of Probability Theory . . . . . . . . . . . . . . . . 18
1.7 Basics of Computability Theory . . . . . . . . . . . . . . 24
1.8 The Roots of Kolmogorov Complexity . . . . . . . . . . . 47
1.9 Randomness . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.10 Prediction and Probability . . . . . . . . . . . . . . . . . 59
1.11 Information Theory and Coding . . . . . . . . . . . . . . 65
1.12 State × Symbol Complexity . . . . . . . . . . . . . . . . 90
1.13 History and References . . . . . . . . . . . . . . . . . . .
2 Algorithmic Complexity 92
2.1 The Invariance Theorem . . . . . . . . . . . . . . . . . . 104
2.2 Incompressibility . . . . . . . . . . . . . . . . . . . . . . . 116
2.3 C as an Integer Function . . . . . . . . . . . . . . . . . . 126
2.4 Random Finite Sequences . . . . . . . . . . . . . . . . . . 133
2.5 *Random Infinite Sequences . . . . . . . . . . . . . . . . 143
2.6 Statistical Properties of Finite Sequences . . . . . . . . . 165
2.7 Algorithmic Properties of C
2.8 Algorithmic Information Theory . . . . . . . . . . . . . . 186
2.9 History and References . . . . . . . . . . . . . . . . . . . 192
3 Algorithmic Prefix Complexity 197
3.1 The Invariance Theorem . . . . . . . . . . . . . . . . . . 200
3.2 *Sizes of the Constants . . . . . . . . . . . . . . . . . . . 206
3.3 Incompressibility . . . . . . . . . . . . . . . . . . . . . . . 211
3.4 K as an Integer Function . . . . . . . . . . . . . . . . . . 216
3.5 Random Finite Sequences . . . . . . . . . . . . . . . . . . 218
3.6 *Random Infinite Sequences . . . . . . . . . . . . . . . . 220
3.7 Algorithmic Properties of K . . . . . . . . . . . . . . . . 239
3.8 *Complexity of Complexity . . . . . . . . . . . . . . . . . 241
3.9 *Symmetry of Algorithmic Information . . . . . . . . . . 244
3.10 History and References . . . . . . . . . . . . . . . . . . . 255
4 Algorithmic Probability 259
4.1 Semicomputable Functions Revisited . . . . . . . . . . . . 260
4.2 Measure Theory . . . . . . . . . . . . . . . . . . . . . . . 262
4.3 Discrete Sample Space . . . . . . . . . . . . . . . . . . . . 265
4.4 Universal Average-Case Complexity . . . . . . . . . . . . 290
4.5 Continuous Sample Space . . . . . . . . . . . . . . . . . . 294
4.6 Universal Average-Case Complexity, Continued . . . . . . 330
4.7 History and References . . . . . . . . . . . . . . . . . . . 331
5 Inductive Reasoning xix 339
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 339
5.2 Solomonoff’s Theory of Prediction . . . . . . . . . . . . . 348
5.3 Simple Pac-Learning . . . . . . . . . . . . . . . . . . . . . 370
5.4 Hypothesis Identification by MDL . . . . . . . . . . . . . 382
5.5 Nonprobabilistic Statistics . . . . . . . . . . . . . . . . . 401
5.6 History and References . . . . . . . . . . . . . . . . . . . 431
6 The Incompressibility Method 441
6.1 Three Examples . . . . . . . . . . . . . . . . . . . . . . . 442
6.2 High-Probability Properties . . . . . . . . . . . . . . . . . 448
6.3 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . 451
6.4 Kolmogorov Random Graphs . . . . . . . . . . . . . . . . 461
6.5 Compact Routing . . . . . . . . . . . . . . . . . . . . . . 469
6.6 Average-Case Analysis of Sorting . . . . . . . . . . . . . . 476
6.7 Longest Common Subsequence . . . . . . . . . . . . . . . 486
6.8 Formal Language Theory . . . . . . . . . . . . . . . . . . 490
6.9 Online CFL Recognition . . . . . . . . . . . . . . . . . . 497
6.10 Turing Machine Time Complexity . . . . . . . . . . . . . 502
6.11 Communication Complexity. . . . . . . . . . . . . . . . 516
6.12 Circuit Complexity . . . . . . . . . . . . . . . . . . . . . 521
6.13 History and References . . . . . . . . . . . . . . . . . . . 524
7 Resource-Bounded Complexity 531
7.1 Mathematical Theory . . . . . . . . . . . . . . . . . . . . 532
7.2 Language Compression . . . . . . . . . . . . . . . . . . . 550
7.3 Computational Complexity . . . . . . . . . . . . . . . . . 562
7.4 Instance Complexity . . . . . . . . . . . . . . . . . . . . . 571
7.5 Kt and Universal Search . . . . . . . . . . . . . . . . . . . 577
7.6 Time-Limited Universal Distributions . . . . . . . . . . . 582
7.7 Logical Depth . . . . . . . . . . . . . . . . . . . . . . . . 589
7.8 History and References . . . . . . . . . . . . . . . . . . . 596
8 Physics, Information, and Computation 601
8.1 Information Theory . . . . . . . . . . . . . . . . . . . . . 602
8.2 Reversible Computation . . . . . . . . . . . . . . . . . . . 629
8.3 Information Distance . . . . . . . . . . . . . . . . . . . . 641
8.4 Normalized Information Distance . . . . . . . . . . . . . . 660
8.5 Thermodynamics . . . . . . . . . . . . . . . . . . . . . . . 674
8.6 Entropy Revisited . . . . . . . . . . . . . . . . . . . . . . 686
8.7 Quantum Kolmogorov Complexity . . . . . . . . . . . . . 696
8.8 Compression in Nature . . . . . . . . . . . . . . . . . . . 711
8.9 History and References . . . . . . . . . . . . . . . . . . . 714
References 723
Index 765
Links
Full Text
[extern file]
