Learning, Compression, and Meta-Complexity
The research formalizes learning and data compression using Kolmogorov complexity to measure inherent information content. It connects these fields by showing how finding a concise explanation for data relates to constructing models. The work explores meta-complexity, linking learning paradigms to computational difficulty and posing open questions about the relationship between complexity estimation and NP problems.