The classical coding theorem in Kolmogorov complexity [Lev74] states that if a string $x$ is sampled with probability $\geq \delta$ by an algorithm with prefix-free domain, then $K(x) \leq \log(1/\delta) + 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$ [LO21] and $pK^{t}$ [LOZ22]. However, establishing a coding theorem for classical (non-probabilistic) notions of time-bounded Kolmogorov complexity, such as $Kt$ complexity [Lev84], 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. 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.