Abstract:
In 1964 Kolmogorov introduced the concept of the complexity of a finite object (for instance, the words in a certain alphabet). He defined complexity as the minimum number of binary signs containing all the information about a given object that are sufficient for its recovery (decoding). This definition depends essentially on the method of decoding. However, by means of the general theory of algorithms, Kolmogorov was able to give an invariant (universal) definition of complexity. Related concepts were investigated by Solomonoff (U.S.A.) and Markov. Using the concept of complexity, Kolmogorov gave definitions of the quantity of information in finite objects and of the concept of a random sequence (which was then defined more precisely by Martin-Löf). Afterwards, this circle of questions developed rapidly. In particular, an interesting development took place of the ideas of Markov on the application of the concept of complexity to the study of quantitative questions in the theory of algorithms. The present article is a survey of the fundamental results connected with the brief remarks above.
Citation:
A. K. Zvonkin, L. A. Levin, “The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms”, Russian Math. Surveys, 25:6 (1970), 83–124
\Bibitem{ZvoLev70}
\by A.~K.~Zvonkin, L.~A.~Levin
\paper The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms
\jour Russian Math. Surveys
\yr 1970
\vol 25
\issue 6
\pages 83--124
\mathnet{http://mi.mathnet.ru/eng/rm5428}
\crossref{https://doi.org/10.1070/RM1970v025n06ABEH001269}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=307889}
\zmath{https://zbmath.org/?q=an:0222.02027}
Linking options:
https://www.mathnet.ru/eng/rm5428
https://doi.org/10.1070/RM1970v025n06ABEH001269
https://www.mathnet.ru/eng/rm/v25/i6/p85
This publication is cited in the following 415 articles:
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira, Lecture Notes in Computer Science, 15364, Theory of Cryptography, 2025, 253
Ming Li, “Caging AI”, J. Comput. Sci. Technol., 40:1 (2025), 1
Mingyang Li, Jan Reimann, “Turing degrees and randomness for continuous measures”, Arch. Math. Logic, 63:1-2 (2024), 39
Markus Pantsar, “Theorem proving in artificial neural networks: new frontiers in mathematical AI”, Euro Jnl Phil Sci, 14:1 (2024)
Mariano Lemus, Ricardo Faleiro, Paulo Mateus, Nikola Paunković, André Souto, “Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines”, Quantum, 8 (2024), 1230
Emirhan Gürpιnar, Andrei Romashchenko, “Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory”, ACM Trans. Comput. Theory, 2024
Zoe Leyva-Acosta, Eduardo Acuña Yeomans, Francisco Hernandez-Quiroz, “An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity”, Entropy, 26:9 (2024), 802
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024, 369
Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov, 2024 IEEE Information Theory Workshop (ITW), 2024, 181
Bruno Bauwens*, Marius Zimand, “Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time”, J. ACM, 70:2 (2023), 1
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, 1039
George Barmpalias, Alexander Shen, “The Kučera–Gács theorem revisited by Levin”, Theoretical Computer Science, 947 (2023), 113693
Laurent Beaudoin, Loïca Avanthey, “How to help digital-native students to successfully take control of their learning: A return of 8 years of experience on a computer science e-learning platform in higher education”, Educ Inf Technol, 28:5 (2023), 5421
Yanyi Liu, Rafael Pass, Lecture Notes in Computer Science, 14082, Advances in Cryptology – CRYPTO 2023, 2023, 645
Rahul Ilango, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 733
Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 458
Adam Case, Christopher P. Porter, “The Intersection of Algorithmically Random Closed Sets and Effective Dimension”, ACM Trans. Comput. Logic, 23:4 (2022), 1
Andrei Romashchenko, “Clustering with respect to the information distance”, Theoretical Computer Science, 929 (2022), 164
Citation in format AMSBIB
Contact us: