Tighter Bounds for Algorithmic Complexity Estimation Using a Reusable Code-Based Block Decomposition Method
For researchers in algorithmic complexity and information theory, this work provides a theoretical extension to BDM that can yield tighter bounds on complexity estimates, though it remains theoretical without empirical validation.
The paper introduces a version of the Block Decomposition Method (BDM) that reduces description length by exploiting dependencies between blocks, formalized as algorithmic attention. It shows that exact optimization is NP-hard, derives conditions for improvement, and relates gains to algorithmic mutual information.
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.