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

Area of Science:

• Information Theory
• Computer Science
• Data Science

Background:

• Algorithmic complexity, particularly Kolmogorov complexity, offers a powerful theoretical framework for understanding information and computation.
• Existing applications range from established statistical lossless compression to emerging, yet challenging, novel techniques.
• A recent minireview presented claims that warrant rebuttal and an alternative perspective.

Purpose of the Study:

• To review and compare established and novel applications of algorithmic complexity.
• To present evidence for the complementary nature of different algorithmic complexity methods.
• To provide a rebuttal to a previous minireview and offer an alternative viewpoint.

Main Methods:

• Review of existing literature on algorithmic (Kolmogorov) complexity applications.
• Comparative analysis of dominant (e.g., statistical compression) and novel approaches.
• Theoretical grounding of methods within algorithmic information theory principles.

Main Results:

• Co-existence and complementarity of various algorithmic complexity techniques across different application regimes.
• Identification of trade-offs between numerical applicability, risk, and relevance in different methods.
• Demonstration of how methods relax conditions for practical application.

Conclusions:

• Algorithmic complexity offers diverse tools for advancing scientific discovery.
• Methodological innovation is encouraged, with a focus on grounding in information theory.
• The paper provides a critical re-evaluation of existing claims and proposes future directions.