Two Decades of Applied Kolmogorov Complexity. In Memoriam: Andrei Nikolaevich Kolmogorov, 1903 - 1987

摘要

The main ideas of Kolmogorov complexity are introduced, and applications of this elegant notion are reviewed. Application of the fact that some strings are compressible includes a strong version of Godel's incompleteness theorem. Applications of lower bound arguments that rest on the fact that certain strings cannot be compressed at all range from Turing machines to electronic chips. Probability theory and a priori probability applications range from foundational issues to the theory of learning and inductive inference in artificial intelligence. Resource-bounded Kolmogorov complexity applications range from NP-completeness and the P versus NP question, to cryptography.