Tighter Bounds for Algorithmic Complexity Estimation Using a Reusable Code-Based Block Decomposition Method
2026-06-22 • Information Theory
Information TheoryComputational Complexity
AI summaryⓘ
The authors improved a method called the Block Decomposition Method (BDM), which estimates the complexity of data by breaking it into parts. Their new version takes advantage of similarities between parts to avoid repeating descriptions, making the overall explanation shorter and more efficient. They explain this process using a concept they call algorithmic attention, where shared information is reused rather than described multiple times. They also analyzed how hard it is to find the best way to reuse information and provided guidance on how to implement their improved method.
Block Decomposition MethodAlgorithmic ComplexityAlgorithmic ProbabilityCoding Theorem MethodShannon EntropyAlgorithmic Mutual InformationNP-hardConditional ComplexityLossless Compression
Authors
Eduardo Yuji Sakabe, Felipe S. Abrahão, Santiago Hernández-Orozco, Ricardo Gudwin, Hector Zenil
Abstract
The Block Decomposition Method (BDM) was introduced as an alternative to popular lossless compression methods such as LZW for estimating algorithmic complexity from the principles of algorithmic probability and classical information theory. It extends the Coding Theorem Method (CTM) from small objects to larger ones by combining local estimates of algorithmic complexity with a global account of repetition based on Shannon entropy. Here, we introduce a version of BDM in which dependencies between blocks are utilized to reduce the length of the description based on reusable program code in the decomposition of an object, and on conditional descriptions capable of accounting for shared structure between observations. We formalize this allocation of descriptive resources as algorithmic attention. Repeated or related components need not be described independently, and the resulting reduction in description length is governed by the amount of shared algorithmic information. We formulate this extension as a reuse optimization problem, show that exact optimization is NP-hard, derive conditions under which it improves upon independent descriptions, relate the achievable gains to algorithmic mutual information, prove the relationship with the previous BDM version, and provide a roadmap for its implementation using CTM-derived complexity and conditional complexity estimates.