A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions

Abstract

Some established and also novel techniques in the field of applications of algorithmic (Kolmogorov) complexity currently co-exist for the first time and are here reviewed, ranging from dominant ones such as statistical lossless compression to newer approaches that advance, complement and also pose new challenges and may exhibit their own limitations. Evidence suggesting that these different methods complement each other for different regimes is presented and despite their many challenges, some of these methods can be better motivated by and better grounded in the principles of algorithmic information theory. It will be explained how different approaches to algorithmic complexity can explore the relaxation of different necessary and sufficient conditions in their pursuit of numerical applicability, with some of these approaches entailing greater risks than others in exchange for greater relevance. We conclude with a discussion of possible directions that may or should be taken into consideration to advance the field and encourage methodological innovation, but more importantly, to contribute to scientific discovery. This paper also serves as a rebuttal of claims made in a previously published minireview by another author, and offers an alternative account.

arXiv comment39 pages; a rebuttal and answer to Paul Vitanyi's review. As accepted by the journal Entropy

References in corpus (7)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
• Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures
• How incomputable is Kolmogorov complexity?
• Algorithmic Networks: central time to trigger expected emergent open-endedness
• Approximations of Algorithmic and Structural Complexity Validate Cognitive-behavioural Experimental Results
• Finite-State Complexity and the Size of Transducers

Cited by in corpus (7)

• A comparison of LSTM and GRU networks for learning symbolic sequences
• Reliability and Interpretability in Science and Deep Learning
• On the Salient Limitations of the Methods of Assembly Theory and their Classification of Molecular Biosignatures
• Emergence and algorithmic information dynamics of systems and observers
• Multiclass classification utilising an estimated algorithmic probability prior
• Generalized Zurek's bound on the cost of an individual classical or quantum computation
• Investigating Estimated Kolmogorov Complexity as a Means of Regularization for Link Prediction