2026-09-08T01:21:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26499 2026-09-05T19:45:24Z ddc:004 open_access

Equivalence Between Coding and Complexity Lower Bounds Hu, Jinqiao Lu, Zhenjian Oliveira, Igor C. meta-complexity lower bounds Kolmogorov complexity The classical coding theorem in Kolmogorov complexity [Levin, 1974] states that if a string x is sampled with probability ≥ δ by an algorithm with prefix-free domain, then 𝖪(x) ≤ log(1/δ) + O(1). Motivated by applications in algorithms, average-case complexity, learning, and cryptography, computationally efficient variants of this result have been established for several recently introduced probabilistic measures of time-bounded Kolmogorov complexity, including rKt [Zhenjian Lu and Igor C. Oliveira, 2021] and pK^t [Zhenjian Lu et al., 2022]. However, establishing a coding theorem for classical (non-probabilistic) notions of time-bounded Kolmogorov complexity, such as Kt complexity [Leonid A. Levin, 1984], remains a longstanding open problem despite its significance. In particular, the current status of coding results reveals a fundamental gap in our understanding of the role of randomness in data compression. In this work, we make progress by establishing the first equivalence between coding for Kt complexity and complexity lower bounds. Specifically, we show that weak coding for polynomial-time samplable distributions with bounds of the form Kt(x) ≤ (1/δ ⋅ |x|)^ε for all ε > 0 holds if and only if EXP ≠ BPP. Building on this equivalence, we show that similar characterizations hold for non-deterministic and zero-error variants of Kt complexity, demonstrating that coding is equivalent to a corresponding complexity separation in each case. We complement these results by establishing additional equivalences involving the computational hardness of approximating time-bounded Kolmogorov complexity, along with an unconditional lower bound on the complexity of approximating zero-error time-bounded Kolmogorov complexity. These results reveal novel connections between coding (the existence of succinct encodings), complexity separations (e.g., NEXP versus BPP), and meta-complexity (the complexity of deciding if a succinct encoding exists). In particular, our work provides a new perspective on frontier questions in complexity theory and explains why coding theorems exist for rKt and pK^t but remain unknown for other measures of time-bounded Kolmogorov complexity. Finally, our results determine the minimal hardness assumptions sufficient for coding in different settings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jinqiao Hu and Zhenjian Lu and Igor C. Oliveira 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.110 urn:nbn:de:0030-drops-264991 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.110 eng https://creativecommons.org/licenses/by/4.0/legalcode