Equivalence Between Coding and Complexity Lower Bounds

Hu, Jinqiao; Lu, Zhenjian; Oliveira, Igor C.

doi:10.4230/LIPIcs.ICALP.2026.110

Equivalence Between Coding and Complexity Lower Bounds

Jinqiao Hu

University of Warwick, UK Zhenjian Lu

University of Victoria, Canada Igor C. Oliveira

University of Warwick, UK

Abstract

The classical coding theorem in Kolmogorov complexity [27] states that if a string $x$ is sampled with probability $\geq\delta$ by an algorithm with prefix-free domain, then $\mathsf{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 $\mathsf{rKt}$ [35] and $\mathsf{pK}^{t}$ [38]. However, establishing a coding theorem for classical (non-probabilistic) notions of time-bounded Kolmogorov complexity, such as $\mathsf{Kt}$ complexity [28], 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 $\mathsf{Kt}$ complexity and complexity lower bounds. Specifically, we show that weak coding for polynomial-time samplable distributions with bounds of the form

\mathsf{Kt}(x)\leq\left(\frac{1}{\delta}\cdot|x|\right)^{\varepsilon}% \textnormal{ for all }\varepsilon>0

holds if and only if $\mathsf{EXP}\neq\mathsf{BPP}$ . Building on this equivalence, we show that similar characterizations hold for non-deterministic and zero-error variants of $\mathsf{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., $\mathsf{NEXP}$ versus $\mathsf{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 $\mathsf{rKt}$ and $\mathsf{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.

Keywords and phrases:

meta-complexity, lower bounds, Kolmogorov complexity

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational complexity and cryptography

Related Version:

Full Version: https://eccc.weizmann.ac.il/report/2025/211/ [20]

Acknowledgements:

We would like to thank Hanlin Ren for discussions related to the problem of showing that

\mathsf{ZPEXP}\nsubseteq\mathsf{ZPP}/_{O(\log n)}

. We also thank the anonymous reviewers for their suggestions on improving the presentation and for their discussion of prior work.

Funding:

This work received support from the UKRI Frontier Research Guarantee Grant
EP/Y007999/1 and the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick.

DOI:

10.4230/LIPIcs.ICALP.2026.110

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

1.1 Context and Motivation

The investigation of data compression problems and their computational complexity has seen significant progress and impact in recent years. In particular, a sequence of works have established that different notions of compression and their associated computational problems can be used to capture major open problems from theoretical computer science. Some notable examples include the existence of one-way functions [30] and secure key-agreement protocols [6] in cryptography, and the efficient learnability of Boolean circuits [9] and the complexity of inductive inference [19] in computational learning theory. Strikingly, for several statements that do not refer to compression, the only known proof of the result seems to crucially rely on ideas and techniques from compression. Among them, we have the existence of learning speedups [41], a connection between worst-case and average-case complexity [13], and lower bounds on program size overhead in indistinguishability obfuscation [34].

A central tool in the study of compression is the coding theorem from Kolmogorov complexity [27]. It states that if a string $x\in\{0,1\}^{n}$ is sampled with probability $\geq\delta$ by an algorithm with prefix-free domain then $\mathsf{K}(x)\leq\log(1/\delta)+O(1)$ . This general result connects randomized computations to compression and is widely considered to be one of the pillars of the theory of Kolmogorov complexity [26].

Due to the time-unbounded nature of Kolmogorov complexity, the coding theorem as stated above is typically not sufficient in algorithmic applications where the running time of algorithms is relevant. A few years ago, [35, 38] established a similar result for certain time-bounded variants of Kolmogorov complexity, namely, $\mathsf{rKt}$ and $\mathsf{pK}^{t}$ complexities. Since then, these results have found several applications in cryptography [21, 31, 15, 18, 17, 33], algorithm design and hardness results [16, 37, 11], average-case complexity [38, 39], learning theory [12, 19, 10], and complexity lower bounds [14, 42, 32].

While unconditional, a drawback of these coding results is that $\mathsf{rKt}$ and $\mathsf{pK}^{t}$ are probabilistic notions of time-bounded Kolmogorov complexity [36], meaning that randomness (and consequently uncertainty) is essential to the representation of the string $x$ . Establishing a coding theorem for classical (non-probabilistic) notions of time-bounded Kolmogorov complexity, such as Levin’s $\mathsf{Kt}$ complexity [28], remains a longstanding open problem. It provides a natural computational setting where randomness offers a significant advantage over deterministic computations given our current knowledge of algorithms and complexity theory.

Let $\kappa$ be a measure of (time-bounded) Kolmogorov complexity, such as $\mathsf{Kt}$ , $\mathsf{rKt}$ , etc. Let $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ be a polynomial-time samplable distribution family. In order to put our results in perspective, we can informally classify coding theorems according to the amount of compression they achieve:

$\blacksquare$

Optimal Coding: $\kappa(x)\leq\log(1/\mathcal{D}_{n}(x))+O(\log n)$ . This is known for $\kappa\in\{\mathsf{K},\mathsf{pK}^{t}\}$ [28, 38].
$\blacksquare$

Near-Optimal Coding: $\kappa(x)\leq O(\log(1/\mathcal{D}_{n}(x))+\log n)$ . This is known for $\kappa=\mathsf{rKt}$ [35, 38].
$\blacksquare$

Weak Coding: $\kappa(x)\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n\right)^{\varepsilon}$ , for a fixed but arbitrarily small $\varepsilon>0$ .
$\blacksquare$

Non-Trivial Coding: $\kappa(x)\leq n-\omega(\log n)$ assuming, say, $x$ is generated with probability $\mathcal{D}_{n}(x)\geq 0.99$ .

For non-probabilistic measures of time-bounded Kolmogorov complexity, conditional results are known:

$\blacksquare$

Antunes and Fortnow [3] established that optimal coding holds for $\mathsf{K}^{t}$ under the assumption that exponential time is not infinitely often in subexponential space.
$\blacksquare$

Under the existence of pseudorandom generators of exponential stretch secure against non-uniform circuits, near-optimal coding holds for $\mathsf{Kt}$ (e.g., by combining [35] and [12, Section A.2]).
$\blacksquare$

In the other direction, Lee [26, Chapter 5] proved that if optimal coding holds for $\mathsf{K}^{\mathsf{poly}}$ then $\mathsf{EXP}\neq\mathsf{BPP}$ .

There is a sharp contrast between the unconditional results established for probabilistic measures such as $\mathsf{rKt}$ and $\mathsf{pK}^{t}$ , and the conditional results known for non-probabilistic measures such as $\mathsf{Kt}$ , which require strong computational assumptions. Motivated by this discrepancy and with the goal of advancing our understanding of randomness in computation, we systematically investigate the prospects of achieving better coding results in time-bounded Kolmogorov complexity. From a technical perspective, we are interested in the following basic questions:

(1)

Is it possible to show non-trivial coding for $\mathsf{Kt}$ without hardness assumptions?
(2)

If non-trivial coding for $\mathsf{Kt}$ is difficult to achieve, can we at least improve the existing coding result for $\mathsf{rKt}$ in order to achieve zero-error encodings?
(3)

Is there a connection between coding (i.e., the existence of succinct encodings) and the hardness of the corresponding meta-computational problem (i.e., the task of deciding if a succinct encoding exists)?

More broadly, we seek to deepen our knowledge of the role of randomness in data compression and identify when it can be eliminated without incurring significant overhead, under minimal hardness assumptions.

1.2 Results

Summary.

Our main contribution is to show that coding and complexity lower bounds are in fact equivalent. As a consequence of our results and techniques, we also establish a surprising equivalence between weak coding and non-trivial coding for different measures of time-bounded Kolmogorov complexity. Finally, we extend these equivalences by considering the computational complexity of estimating time-bounded Kolmogorov complexity. This extends our results and uncovers a novel connection between the existence of succinct encodings (coding) and the feasibility of deciding when a succinct encoding exists (meta-complexity).

Altogether, our results completely answer Questions 1-3 stated above. They also show that the validity of a key property (coding) of Kolmogorov complexity in the time-bounded setting captures several frontier questions in complexity theory. This exhibits another significant example of the relevance of compression to central questions in theoretical computer science.

Organization.

In Section 1.2.1, we establish the equivalence between coding and complexity lower bounds for $\mathsf{Kt}$ complexity. Section 1.2.2 and Section 1.2.3 extend these results to the non-deterministic and zero-error variants, denoted by $\mathsf{nKt}$ and $\mathsf{zKt}$ , respectively. The computational complexity of estimating time-bounded Kolmogorov complexity is explored in Section 1.2.4.

1.2.1 Coding for Deterministic Time-Bounded Kolmogorov Complexity

Fix an efficient universal machine $U$ . Recall that for a string $x\in\{0,1\}^{*}$ , we let

\mathsf{Kt}(x)\triangleq\min_{p\in\{0,1\}^{*},\;t\in\mathbb{N}}\Big\{|p|+% \lceil\log t\rceil\colon U^{t}(p)=x\Big\}.

The notation $U^{t}(p)$ denotes the output of $U$ on input string $p$ when it computes for at most $t$ steps. It is also possible to consider a relativized version of $\mathsf{Kt}$ , namely $\mathsf{Kt}^{\mathcal{O}}$ , where we give the universal Turing machine $U$ oracle access to the set $\mathcal{O}\subseteq\{0,1\}^{*}$ .

Recall that an ensemble $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ of distributions $\mathcal{D}_{n}$ supported over $\{0,1\}^{*}$ is polynomial-time samplable if there is a polynomial-time randomized algorithm $A$ whose output $A(1^{n},r)$ for $r\sim\{0,1\}^{*}$ is distributed according to $\mathcal{D}_{n}$ . We denote the probability of an element $x$ over $\mathcal{D}_{n}$ by $\mathcal{D}_{n}(x)\in[0,1]$ .

Theorem 1.

The following statements are equivalent.

1.

$\mathsf{EXP}\neq\mathsf{BPP}$ .
2.

(Weak coding for $\mathsf{Kt}$ .) For any $\varepsilon>0$ and any polynomial-time samplable distribution family $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ , there are infinitely many $n\in\mathbb{N}$ such that for all $x\in\mathsf{Support}(\mathcal{D}_{n})$ ,

$\mathsf{Kt}(x)\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n\right)^{% \varepsilon}.$
3.

(Non-trivial coding for $\mathsf{Kt}$ .) There exists a constant $c>0$ such that the following holds. Let $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ be a polynomial-time samplable distribution family, where each $\mathcal{D}_{n}$ is supported over $\{0,1\}^{n}$ , satisfying that there exists a sequence $\{x_{n}\}_{n\in\mathbb{N}}$ such that $\mathcal{D}_{n}(x_{n})\geq 1-n^{-c}$ for every $n$ . Then for infinitely many $n$ , we have

$\mathsf{Kt}(x_{n})\leq n-\omega(\log n).$

As a consequence of this result, merely showing that $\mathsf{Kt}$ admits non-trivial coding requires a hardness assumption. This addresses Question 1 from Section 1.1.

The equivalence stated in Theorem 1 significantly strengthens a result from [26, Chapter 5] showing that optimal coding for $\mathsf{K}^{\mathsf{poly}}$ yields $\mathsf{EXP}\neq\mathsf{BPP}$ . In addition, our proof that Item 3 implies Item 1 is considerably simpler.

Theorem 1 also establishes an equivalence between weak coding and non-trivial coding for $\mathsf{Kt}$ . On the other hand, we observe in Section 3.2 that near-optimal coding for $\mathsf{Kt}$ implies the significantly stronger separation $\mathsf{DTIME}[2^{O(n)}]\nsubseteq\mathsf{i.o.BPTIME}[2^{n}]$ . Consequently, in contrast to the equivalence between non-trivial coding and weak coding, we are unlikely to obtain an equivalence between weak-coding and near-optimal coding given our current knowledge of complexity theory, unless we can show how to boost the separation $\mathsf{EXP}\neq\mathsf{BPP}$ to a much stronger result.¹¹1In fact, it seems plausible that near-optimal coding for $\mathsf{Kt}$ is equivalent to lower bounds of the form $\mathsf{DTIME}[2^{O(n)}]\nsubseteq\mathsf{BPTIME}[2^{n}]$ . However, it is unclear to us how to establish this equivalence using our techniques, which are based on the theory of computational pseudorandomness.

We derive the following consequence from Theorem 1.

Corollary 2.

The following statements are equivalent:

1.

$\mathsf{EXP}\neq\mathsf{BPP}$ .
2.

For any sequence of strings $\{x_{n}\}_{n\geq 1}$ where $|x_{n}|=n$ and $\mathsf{rKt}(x_{n})\leq O(\log n)$ for each $n$ , there exists infinitely many $n$ such that $\mathsf{Kt}(x_{n})\leq n-\omega(\log n)$ .

This corollary might be compared with [40, Theorem 5], which shows a partial equivalence between a strong derandomization assumption (roughly $\mathsf{BPE}=\mathsf{E}$ ) and a linear relationship between $\mathsf{rKt}$ and $\mathsf{Kt}$ (i.e. $\forall x,\mathsf{Kt}(x)=O(\mathsf{rKt}(x))$ ). However, while [40, Theorem 5] has a gap between the two directions, our result establishes a full equivalence. Corollary 2 follows from Theorem 1 by noting that weak coding for $\mathsf{Kt}$ $\implies$ Corollary 2 Item 2 $\implies$ non-trivial coding for $\mathsf{Kt}$ ,²²2The only nontrivial (but standard) observation is that a universal time-bounded sampler can output any string of $\mathsf{rKt}$ complexity $O(\log n)$ with probability $\geq 1/\mathsf{poly}(n)$ . This is used in the proof of the first implication. which implies that all statements are equivalent. It is unclear to us how to establish Corollary 2 using the techniques from [40, Theorem 5].

1.2.2 Coding for Non-Deterministic Time-Bounded Kolmogorov Complexity

Next, we establish an equivalence between coding with non-deterministic encodings and complexity lower bounds. We will need the following definition, which offers a natural extension of $\mathsf{Kt}$ to the setting of non-deterministic computations. For a string $x\in\{0,1\}^{*}$ , the non-deterministic time-bounded Kolmogorov complexity of $x$ is defined as

\mathsf{nKt}(x)\triangleq\min_{p\in\{0,1\}^{*},\,t\in\mathbb{N}}\left\{|p|+% \lceil\log t\rceil\,\,\middle|\,\,\begin{tabular}[]{@{\textbullet\enspace}l}$% \forall w\in\{0,1\}^{t}$, $U(p,w)$ outputs $x$ or $\bot$ within $t$ steps\\ $\exists w\in\{0,1\}^{t}$, $U(p,w)$ outputs $x$ within $t$ steps\end{tabular}% \right\}.

The above definition is equivalent to a “local” notion of non-deterministic Kolmogorov complexity investigated in [2], which considers instead individual bits of $x$ (see [20, Appendix A]).

Theorem 3.

The following statements are equivalent.

1.

$\mathsf{NEXP}\neq\mathsf{BPP}$ .
2.

(Weak coding for $\mathsf{nKt}$ ) For any $\varepsilon>0$ and any polynomial-time samplable distribution family $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ , there are infinitely many $n\in\mathbb{N}$ such that for all $x\in\mathsf{Support}(\mathcal{D}_{n})$ ,

$\mathsf{nKt}(x)\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n\right)^{% \varepsilon}.$
3.

(Non-trivial coding for $\mathsf{nKt}$ .) There exists a constant $c>0$ such that the following holds. Let $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ be a polynomial-time samplable distribution family, where each $\mathcal{D}_{n}$ is supported over $\{0,1\}^{n}$ , satisfying that there exists a sequence $\{x_{n}\}_{n\in\mathbb{N}}$ such that $\mathcal{D}_{n}(x_{n})\geq 1-n^{-c}$ for every $n$ . Then for infinitely many $n$ , we have

$\mathsf{nKt}(x_{n})\leq n-\omega(\log n).$

Moreover, the above holds if we replace $\mathsf{NEXP}$ with $\mathsf{EXP}^{\mathsf{NP}}$ , and $\mathsf{nKt}$ with $\mathsf{Kt}^{\mathsf{NP}}$ .³³3Recall that $\mathsf{Kt}^{\mathsf{NP}}$ denotes the extension of $\mathsf{Kt}$ where the universal machine $U$ has access to a $\mathsf{SAT}$ oracle.

As a consequence of this result, even if we could achieve non-trivial coding using non-deterministic encodings, a new complexity lower bound would follow. Indeed, Theorem 3 provides a new characterization of the $\mathsf{NEXP}$ versus $\mathsf{BPP}$ problem as a statement about the existence of succinct encodings.

1.2.3 Coding for Zero-Error Time-Bounded Kolmogorov Complexity

Finally, we introduce a natural zero-error variant of $\mathsf{Kt}$ complexity, which can also be seen as the restriction of $\mathsf{rKt}$ [40] to errorless encodings. To the best of our knowledge, this definition has not been considered in previous work. For a string $x\in\{0,1\}^{*}$ , we let

\mathsf{zKt}(x)\triangleq\min_{p\in\{0,1\}^{*},\,t\in\mathbb{N}}\left\{|p|+% \lceil\log t\rceil\,\,\middle|\,\,\begin{tabular}[]{@{\textbullet\enspace}l}$% \forall r\in\{0,1\}^{t}$, $U(p,r)$ outputs $x$ or $\bot$ within $t$ steps\\ $\operatorname*{{\bf Pr}}_{r}[U(p,r)$ outputs $x$ within $t$ steps$]\geq\frac{% 2}{3}$\end{tabular}\right\}.

We observe that the existing near-optimal coding result for $\mathsf{rKt}$ [35] yields zero-error encodings whenever the distribution $\mathcal{D}_{n}$ is flat, i.e., when it is uniformly distributed over a set $S\subseteq\{0,1\}^{n}$ (see [20, Section 5.3]). In contrast, our next result indicates that it will be difficult to extend this zero-error coding theorem to all polynomial-time samplable distributions, even in the non-trivial coding regime.

Theorem 4.

The following statements are equivalent.

1.

$\mathsf{prZPEXP}\neq\mathsf{prBPP}$ .
2.

(Weak coding for $\mathsf{zKt}$ ) For any $\varepsilon>0$ and any polynomial-time samplable distribution family $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ , there are infinitely many $n\in\mathbb{N}$ such that for all $x\in\mathsf{Support}(\mathcal{D}_{n})$ ,

$\mathsf{zKt}(x)\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n\right)^{% \varepsilon}.$
3.

(Non-trivial coding for $\mathsf{zKt}$ ) There exists a constant $c>0$ such that the following holds. Let $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ be a polynomial-time samplable distribution family, where each $\mathcal{D}_{n}$ is supported over $\{0,1\}^{n}$ , satisfying that there exists a sequence $\{x_{n}\}_{n\in\mathbb{N}}$ such that $\mathcal{D}_{n}(x_{n})\geq 1-n^{-c}$ for every $n$ . Then for infinitely many $n$ , we have

$\mathsf{zKt}(x_{n})\leq n-\omega(\log n).$

Therefore, obtaining a zero-error version of existing coding results yields a new complexity separation. This addresses Question 2 from Section 1.1. Note that zero-error coding (Theorem 4) implies a stronger separation than non-deterministic coding (Theorem 3), which is expected since $\mathsf{nKt}(x)\leq\mathsf{zKt}(x)$ for every string $x$ (i.e., it is more challenging to achieve a zero-error encoding).

For the interested reader, in [20, Section 5.2] we investigate the possibility of achieving the stronger separation $\mathsf{ZPEXP}\neq\mathsf{BPP}$ from coding for $\mathsf{zKt}$ .

1.2.4 Complexity Separations and Meta-Complexity

Let $\mathsf{MKtP}$ be the following problem: Given $(x,1^{s})$ , where $x\in\{0,1\}^{*}$ and $s\in\mathbb{N}$ , decide whether $\mathsf{Kt}(x)\leq s$ . We also consider a parametrized “gap” version of $\mathsf{MKtP}$ . Let $s_{1},s_{2}\colon\mathbb{N}\to\mathbb{N}$ be such that $s_{1}(n)<s_{2}(n)$ for every large $n$ . Define $\mathsf{MKtP}[s_{1},s_{2}]$ as the problem of deciding, given $x\in\{0,1\}^{n}$ , whether $\mathsf{Kt}(x)\leq s_{1}(n)$ or $\mathsf{Kt}(x)\geq s_{2}(n)$ . When $s_{1}(n)=n^{\varepsilon}$ and $s_{2}(n)=n-1$ , we might informally refer to the problem as $\mathsf{Gap}$ - $\mathsf{MKtP}$ .

Similarly, we can define analogous problems for $\mathsf{nKt}$ , $\mathsf{Kt}^{\mathsf{NP}}$ , and $\mathsf{zKt}$ , denoted as $\mathsf{MnKtP}$ , $\mathsf{MKt^{\mathsf{NP}}P}$ , and $\mathsf{MzKtP}$ , respectively.

We identify these problems with their corresponding (promise) languages in a natural way.

The problem $\mathsf{Gap}$ - $\mathsf{MKtP}$ is complete for $\mathsf{EXP}$ under non-uniform polynomial-time reductions [1]. A similar result also holds for $\mathsf{Gap}$ - $\mathsf{MnKtP}$ , i.e., $\mathsf{Gap}$ - $\mathsf{MnKtP}$ is complete for $\mathsf{NEXP}/_{\mathsf{poly}}$ under non-uniform polynomial-time reductions [2]. These results imply that $\mathsf{EXP}\not\subseteq\mathsf{P}/{{}_{\mathsf{poly}}}$ (resp. $\mathsf{NEXP}\not\subseteq\mathsf{P}/{{}_{\mathsf{poly}}}$ ) if and only if $\mathsf{Gap}$ - $\mathsf{MKtP}\not\not\in\mathsf{P}/{{}_{\mathsf{poly}}}$ (resp, $\mathsf{Gap}$ - $\mathsf{MnKtP}\not\in\mathsf{P}/{{}_{\mathsf{poly}}}$ ).

On the other hand, it was also established that $\mathsf{Gap}$ - $\mathsf{MKtP}$ captures the hardness of $\mathsf{EXP}$ with respect to uniform randomized algorithms. That is, $\mathsf{EXP}\neq\mathsf{BPP}$ if and only if $\mathsf{Gap}$ - $\mathsf{MKtP}\not\in\mathsf{prBPP}$ [1]. Here, we extend this result to the notion of $\mathsf{nKt}$ .

Theorem 5.

The following are equivalent.

1.

$\mathsf{NEXP}\neq\mathsf{BPP}$ .
2.

$\mathsf{MnKtP}[n^{\varepsilon},n-1]\notin\mathsf{prBPP}$ , for all $\varepsilon>0$ .

Moreover, the above holds if we replace $\mathsf{MnKtP}$ with $\mathsf{MKt^{\mathsf{NP}}P}$ , and $\mathsf{NEXP}$ with $\mathsf{EXP}^{\mathsf{NP}}$ .⁴⁴4In fact, in all these results, the proof implicitly shows that the gap version of the problem is easy if and only if the non-gap version is easy. For instance, it is known that $\mathsf{Gap}$ - $\mathsf{MKtP}\notin\mathsf{prBPP}$ if and only if $\mathsf{MKtP}\notin\mathsf{BPP}$ . This will also be the case for the equivalences established in this paper.

For zero-error time bounded Kolmogorov complexity, we show that the problem of approximating $\mathsf{zKt}$ is at least as hard as solving every problem in $\mathsf{prZPEXP}$ with respect to two-sided error randomized algorithms.

Theorem 6.

If $\mathsf{MzKtP}[n^{\varepsilon},n-1]\in\mathsf{prBPP}$ for some $\varepsilon>0$ , then $\mathsf{prZPEXP}=\mathsf{prBPP}$ .

Finally, we obtain an unconditional lower bound for approximating $\mathsf{zKt}$ against zero-error randomized algorithms.

Theorem 7.

$\mathsf{MzKtP}[n^{\varepsilon},n-1]\not\in\mathsf{prZPTIME}\left[2^{\mathsf{% polylog}(n)}\right]$ , for all $\varepsilon>0$ .

Theorem 7 builds on a lower bound for approximating $\mathsf{rKt}$ from [40] (i.e., $\mathsf{MrKtP}\notin\mathsf{BPP}$ ). Since $\mathsf{zKt}$ is an intermediate measure between $\mathsf{Kt}$ and $\mathsf{rKt}$ , in a sense, the result can be seen as progress towards showing that $\mathsf{MKtP}\notin\mathsf{P}$ . The latter is a well-known open problem in meta-complexity (see, e.g., [1]).

1.3 Summary of Equivalences and Concluding Remarks

For convenience of the reader, we summarize the equivalences established in this paper in Table 1. Note that, from the perspective of derandomization, our results identify the minimal complexity-theoretic assumptions required to obtain coding for different measures of Kolmogorov complexity.

Table 1: Summary of Equivalences: In each row, the three items are equivalent, except for the last row, where the complexity separation and the coding theorem are equivalent, and they imply that probabilistic polynomial-time algorithms cannot approximate

\mathsf{zKt}

(

\mathsf{Gap}

-

\mathsf{MzKtP}\not\in\mathsf{prBPP}

).

Complexity Separation	Coding Theorem	Meta-Complexity
$\mathsf{EXP}\neq\mathsf{BPP}$	Weak/Non-Trivial Coding for $\mathsf{Kt}$	$\mathsf{Gap}\text{-}\mathsf{MKtP}\not\in\mathsf{prBPP}$
$\mathsf{NEXP}\neq\mathsf{BPP}$	Weak/Non-Trivial Coding for $\mathsf{nKt}$	$\mathsf{Gap}\text{-}\mathsf{MnKtP}\not\in\mathsf{prBPP}$
$\mathsf{EXP}^{\mathsf{NP}}\neq\mathsf{BPP}$	Weak/Non-Trivial Coding for $\mathsf{Kt}^{\mathsf{NP}}$	$\mathsf{Gap}\text{-}\mathsf{MKt^{\mathsf{NP}}P}\not\in\mathsf{prBPP}$
$\mathsf{prZPEXP}\neq\mathsf{prBPP}$	Weak/Non-Trivial Coding for $\mathsf{zKt}$	$\Longrightarrow\mathsf{Gap}\text{-}\mathsf{MzKtP}\not\in\mathsf{prBPP}$

As mentioned above, the equivalence between $\mathsf{EXP}\neq\mathsf{BPP}$ and $\mathsf{Gap}$ - $\mathsf{MKtP}\not\in\mathsf{prBPP}$ included in the first row of Table 1 was established in [1]. It is unclear to us how to prove that $\mathsf{Gap}$ - $\mathsf{MzKtP}\in\mathsf{prBPP}$ from $\mathsf{prZPEXP}=\mathsf{prBPP}$ , which would provide the equivalence between all items in the last row of Table 1.

Figure 1: An arrow from a Kolmogorov complexity measure

\kappa_{1}

to

\kappa_{2}

indicates that

\kappa_{1}(x)\leq\kappa_{2}(x)

for every string

x

. Our results show that, for each measure

\kappa

, the existence of weak coding and a corresponding complexity separation against

\mathsf{BPP}

are equivalent (see Table 1). In particular, for

\kappa\in\{\mathsf{K},\mathsf{rKt}\}

, both coding and lower bounds are known, while for

\kappa\in\{\mathsf{Kt}^{\mathsf{NP}},\mathsf{nKt},\mathsf{zKt},\mathsf{Kt}\}

, these remain longstanding challenges.

In contrast to the equivalences described in Table 1, for the two-sided error notion of time-bounded Kolmogorov complexity $\mathsf{rKt}$ , we know unconditionally that:

$\blacksquare$

$\mathsf{BPEXP}\nsubseteq\mathsf{BPP}$ (see, e.g., [7] and references therein);
$\blacksquare$

a near-optimal coding theorem holds [35]; and
$\blacksquare$

$\mathsf{Gap}$ - $\mathsf{MrKtP}\notin\mathsf{prBPP}$ [40].

Our work highlights that this is not a coincidence, i.e., these different statements are intimately related (see Figure 1). Moreover, our results provide an equivalence between coding (i.e., the existence of succinct encodings) and the hardness of the corresponding meta-computational problem (i.e., the task of deciding if a succinct encoding exists). In other words, they answer affirmatively Question 3 stated in Section 1.1.

Finally, our results show that any non-trivial compression (even with nondeterminism) would imply new separations in complexity theory and advance our understand of the power and limits of randomness in computation. It would be worthwhile to investigate whether this perspective can be combined with other techniques and employed as a concrete method for establishing new lower bounds.

1.4 Techniques

In this section, we explain the main ideas behind our proofs. We start off with our results for $\mathsf{Kt}$ complexity. We then discuss the non-deterministic and zero-error settings, which require additional ideas and more elaborate proofs. In particular, the techniques we develop to establish our results in the context of zero-error Kolmogorov complexity might be of independent interest.

Equivalence Between Coding for $\mathsf{Kt}$ and $\mathsf{EXP}\neq\mathsf{BPP}$ .

We first describe how to obtain $\mathsf{EXP}\neq\mathsf{BPP}$ from a non-trivial coding theorem for $\mathsf{Kt}$ . Note that, by a standard padding argument, it suffices to show that $\mathsf{EE}\neq\mathsf{BPE}$ , where $\mathsf{EE}\triangleq\mathsf{DTIME}[2^{2^{O(n)}}]$ and $\mathsf{BPE}\triangleq\mathsf{BPTIME}[2^{O(n)}]$ . Our goal is then to diagonalize against $\mathsf{BPE}$ within $\mathsf{EE}$ . The first observation is that if we have a non-trivial coding theorem for $\mathsf{Kt}$ , then the truth table of every language in $\mathsf{BPE}$ on $n$ -bit inputs will have $\mathsf{Kt}$ complexity strictly less than $2^{n}$ , for infinitely many $n$ . To see this, consider any language $L\in\mathsf{BPE}$ and a sampler $A$ that, on input $1^{N}$ , aims to output the $N$ -bit truth table of $L^{=n}$ , where $n=\log N$ ,⁵⁵5For simplicity, let’s assume that $N$ is always a power of two. by running a probabilistic machine for computing $L$ on every input in $\{0,1\}^{n}$ . It is not hard to see that $A(1^{N})$ can be implemented to run in time $\mathsf{poly}(N)$ and outputs $\mathsf{tt}(L^{=n})$ with probability at least $1-1/\mathsf{poly}(N)$ . Then, by invoking the non-trivial coding theorem for $\mathsf{Kt}$ on this sampler, we get that for infinitely many $n$ , $\mathsf{Kt}(\mathsf{tt}(L^{=n}))\leq 2^{n}-\omega(n)$ . Note that this holds for every $L\in\mathsf{BPE}$ . To diagonalize against all such $L$ , we define a language $L_{\mathsf{hard}}$ whose $2^{n}$ -bit truth table has $\mathsf{Kt}$ complexity at least $2^{n}-1$ for all $n$ . Since one can compute an $N$ -bit string with $\mathsf{Kt}$ complexity at least $N-1$ in time $\mathsf{poly}(2^{N})$ using exhaustive search, it follows that $L_{\mathsf{hard}}$ is computable in $\mathsf{EE}$ .

To derive a non-trivial coding theorem for $\mathsf{Kt}$ from $\mathsf{EXP}\neq\mathsf{BPP}$ , the main idea is to use the hardness-vs-randomness framework to construct a pseudorandom generator (PRG). More specifically, by classical results in [23, 43], we obtain that if $\mathsf{PSPACE}\neq\mathsf{BPP}$ , then for every $b,c>0$ , there exists a PRG $G$ that takes a short seed of length $n^{1/b}$ , runs in time $2^{O(n^{1/b})}$ , and outputs a longer string of length $n^{c}$ that can fool any $n^{b}$ -time algorithm $D$ , for infinitely many $n$ . More formally:

\left|\operatorname*{{\bf Pr}}_{z\sim\{0,1\}^{n^{1/b}}}[D(G(z))=1]-% \operatorname*{{\bf Pr}}_{u\sim\{0,1\}^{n^{c}}}[D(u)=1]\right|\leq\frac{1}{n^{% b}}.

Let $\mathcal{D}\triangleq\{\mathcal{D}_{n}\}$ be a polynomial-time samplable distribution family and $A$ be its sampler, i.e, $A(u)$ is distributed according to $\mathcal{D}_{n}$ for uniformly random $u\sim\{0,1\}^{n^{c}}$ , where $c>0$ is some constant. Let $x\in\mathsf{Support}(\mathcal{D}_{n})$ be the string for which we aim to find a short encoding. (For simplicity, let’s assume that each $\mathcal{D}_{n}$ is supported on $\{0,1\}^{n}$ .) First observe that the weak coding theorem holds trivially on a given $n$ -bit string $x$ if $\mathcal{D}_{n}(x)<1/n^{1/\varepsilon}$ , since in this case the desired encoding bound is larger than the length of the string. Therefore, we can assume without loss of generality that $\mathcal{D}_{n}(x)\geq 1/n^{1/\varepsilon}$ .

Consider the function $D_{x}$ , defined as $D_{x}(y)=1$ if and only if $A(y)=x$ . Note that $\operatorname*{{\bf Pr}}_{u}[D_{x}(u)=1]\geq 1/n^{1/\varepsilon}$ . Using the pseudorandom property of $G$ (with $b>1/\varepsilon$ chosen sufficiently large), it follows that:

\operatorname*{{\bf Pr}}_{z\sim\{0,1\}^{n^{1/b}}}[D_{x}(G(z))=1]\geq% \operatorname*{{\bf Pr}}_{u\sim\{0,1\}^{n^{c}}}[D_{x}(u)=1]-\frac{1}{n^{b}}>0.

This implies the existence of some $z\in\{0,1\}^{n^{1/b}}$ such that $A(G(z))=x$ . Given the descriptions of $A$ , $G$ , and the seed $z$ , $x$ can be recovered in time $2^{O(n^{1/b})}$ , yielding $\mathsf{Kt}(x)\leq O(n^{1/b})\leq n^{\varepsilon}$ .

However, there is an issue in the above argument: the function $D_{x}$ depends on $x$ , making it non-uniform, while the PRG $G$ is designed to fool only uniform algorithms. The key observation is that the PRG obtained from [23, 43] possesses a slightly stronger property: it not only fools uniform algorithms but in our case also fools $D_{x}$ with probability at least $1-1/n^{b}$ over $x$ sampled from any $n^{b}$ -time samplable distribution (see Theorem 13). Since $x$ is assumed to be sampled from $\mathcal{D}_{n}$ with probability at least $1/n^{1/\varepsilon}$ , we conclude that $G$ can successfully fool $D_{x}$ in this case; otherwise, it would fail with probability at least $1/n^{1/\varepsilon}>1/n^{b}$ , contradicting the pseudorandomness guarantee.

The above requires assuming that $\mathsf{PSPACE}\neq\mathsf{BPP}$ , while we only have $\mathsf{EXP}\neq\mathsf{BPP}$ . We address this with a standard win-win argument. If $\mathsf{PSPACE}\neq\mathsf{BPP}$ , then we are done. Otherwise, if $\mathsf{PSPACE}=\mathsf{BPP}$ , our assumption that $\mathsf{EXP}\neq\mathsf{BPP}$ implies $\mathsf{EXP}\neq\mathsf{PSPACE}$ . By the classical Karp–Lipton result [25], which states that if $\mathsf{EXP}\subseteq\mathsf{SIZE}[\mathsf{poly}]$ , then $\mathsf{EXP}=\mathsf{PSPACE}$ , it follows that $\mathsf{EXP}\not\subseteq\mathsf{SIZE}[\mathsf{poly}]$ . Using a different hardness-vs-randomness framework [5] (see Theorem 12), which allows us to produce pseudorandomness using the hard truth table of a language in $\mathsf{EXP}$ , this also yields an infinitely-often secure PRG with sub-polynomial seed length.⁶⁶6In fact, the PRG obtained in this case can even fool non-uniform algorithms. Such a PRG can be used to achieve weak coding for $\mathsf{Kt}$ as described in previous paragraphs.

Equivalence Between Coding for $\mathsf{nKt}$ and $\mathsf{NEXP}\neq\mathsf{BPP}$ .

To obtain $\mathsf{NEXP}\neq\mathsf{BPP}$ from a non-trivial coding theorem for $\mathsf{nKt}$ , one might consider resembling the proof used in the previous case. However, for this approach to work, we would need to be able to construct an $N$ -bit string with high $\mathsf{nKt}$ -complexity in time $\mathsf{poly}(2^{N})$ , which is not clear how to achieve (even non-deterministically).⁷⁷7Note that a naive algorithm for this task runs in time at least $2^{2^{N}}$ . In other words, we need to consider each candidate nondeterministic program running in time at most $2^{N}$ , and enumerating over all choices of the nondeterministic string to check that the program is suitable takes doubly exponential time. Here, we present a more sophisticated diagonalization argument that bypasses the need for this task. For simplicity, we describe how to obtain $\mathsf{NEXP}\neq\mathsf{BPP}$ from a weak coding theorem for $\mathsf{nKt}$ .

First of all, if we have a weak coding theorem for $\mathsf{nKt}$ , by a similar argument as described in the previous case, we get that the truth table of every language in $\mathsf{BPE}$ on $n$ -bit inputs will have $\mathsf{nKt}$ -complexity less than $2^{\varepsilon n}$ , for infinitely many $n$ . This means one can non-deterministically generate these truth tables in time $2^{2^{\varepsilon n}}$ with at most $2^{\varepsilon n}$ -bits of advice. This allows us to conclude that $\mathsf{BPE}\subseteq\mathsf{i.o.NTIME}\left[2^{2^{\varepsilon n}}\right]/_{2^% {\varepsilon n}}$ .

Now suppose, for the sake of contradiction, $\mathsf{NEXP}=\mathsf{BPP}$ . Note that by the existence of $\mathsf{NE}$ -complete problems under linear-time reductions, this implies $\mathsf{NE}\subseteq\mathsf{BPTIME}[n^{k}]$ for some fixed $k>0$ . Then we have

$\displaystyle\mathsf{EE}$	$\displaystyle\subseteq\mathsf{BPE}$	(by padding and $\mathsf{NEXP}=\mathsf{BPP}$ )
	$\displaystyle\subseteq\mathsf{i.o.NTIME}\left[2^{2^{\varepsilon n}}\right]/_{2% ^{\varepsilon n}}$	(by the previous paragraph)
	$\displaystyle\subseteq\operatorname{\mathsf{i.o.}}\mathsf{BPTIME}\left[2^{k% \cdot\varepsilon\cdot n}\right]/_{2^{\varepsilon n}}$	(by padding and $\mathsf{NE}\subseteq\mathsf{BPTIME}[n^{k}]$ )
	$\displaystyle\subseteq\operatorname{\mathsf{i.o.}}\mathsf{BPTIME}\left[2^{n}% \right]/_{2^{\varepsilon n}}$	(by choosing $\varepsilon\leq 1/k$ )
	$\displaystyle\subseteq\operatorname{\mathsf{i.o.}}\mathsf{DTIME}\left[2^{2^{n}% }\right]/_{2^{\varepsilon n}}$	(by deterministic simulation)

Note that we use the assumption $\mathsf{NEXP}=\mathsf{BPP}$ twice in the above. Finally, one can show by diagonalization that $\mathsf{EE}\not\in\operatorname{\mathsf{i.o.}}\mathsf{DTIME}\left[2^{2^{n}}% \right]/_{2^{\varepsilon n}}$ , which gives a contradiction as desired.

The proof that weak coding for $\mathsf{nKt}$ follows from $\mathsf{NEXP}\neq\mathsf{BPP}$ is similar to the previous case. We use the hardness-vs-randomness framework (and a win-win argument) to construct a PRG that “hits” any string $x$ sampled with probability at least $1/\mathrm{poly}(n)$ . However, there are a couple of differences in this setting. First, in the win-win argument, we use the Karp–Lipton result for $\mathsf{NEXP}$ [22] instead of the one for $\mathsf{EXP}$ . Second, to obtain weak coding for $\mathsf{nKt}$ , we require our PRG to be computable non-deterministically in the sense that there exists some good guess $w$ that allows us to correctly compute the output of the PRG, while for all other bad guesses, we output $\bot$ . While we don’t know how to achieve this exactly, we can show that it is possible with access to a small advice string. This is because one can non-deterministically construct the truth table of a language in $\mathsf{NEXP}$ using a small amount of advice that indicates the number of positive instances, as observed for instance in [22]. Such a PRG is sufficient for our purposes.

Equivalence Between Coding for $\mathsf{zKt}$ and $\mathsf{prZPEXP}\neq\mathsf{prBPP}$ .

The task of obtaining $\mathsf{prZPEXP}\neq\mathsf{prBPP}$ from a non-trivial coding theorem for $\mathsf{zKt}$ faces the same challenge as in the case of showing $\mathsf{NEXP}\neq\mathsf{BPP}$ from a coding theorem for $\mathsf{nKt}$ , since it is unclear how to construct an $N$ -bit string with high $\mathsf{zKt}$ -complexity in time $\mathsf{poly}(2^{N})$ . On the other hand, the alternative approach used to show the latter can also be applied in this context. However, when using this approach in the case of $\mathsf{NEXP}$ , it relied on the fact that $\mathsf{NEXP}$ is a syntactic class, whereas $\mathsf{ZPEXP}$ is not (i.e., it is semantic). To address this issue, we consider the weaker conclusion that $\mathsf{prZPEXP}\neq\mathsf{prBPP}$ instead of $\mathsf{ZPEXP}\neq\mathsf{BPP}$ .

A bigger challenge arises in showing that weak coding for $\mathsf{zKt}$ follows from $\mathsf{prZPEXP}\neq\mathsf{prBPP}$ . Recall that in previous cases, we needed to use a Karp–Lipton result for either $\mathsf{EXP}$ or $\mathsf{NEXP}$ . However, we do not have such a Karp–Lipton result for zero-error probabilistic classes. In fact, obtaining Karp–Lipton theorems for probabilistic classes is known to be a challenging task in complexity theory. While there are known results showing some weak versions of such a theorem for $\mathsf{ZPEXP}$ (see [41]), they are not sufficient for our purpose here.

Note that we only need the Karp–Lipton result in one of the cases in our win-win argument. Specifically, we can consider two cases: $\mathsf{EXP}\neq\mathsf{BPP}$ , in which we have weak coding for $\mathsf{Kt}$ and hence for $\mathsf{zKt}$ , and $\mathsf{EXP}=\mathsf{BPP}$ . We show that in the latter case, we can indeed obtain a Karp–Lipton theorem for zero-error probabilistic classes. More specifically, we show that assuming $\mathsf{EXP}=\mathsf{BPP}$ , if $\mathsf{ZPE}/_{n}\subseteq\mathsf{SIZE}[n^{k}]$ for some $k>0$ , then $\mathsf{prZPEXP}=\mathsf{prEXP}$ (see [20, Lemma 35]).

Now assume $\mathsf{prZPEXP}\neq\mathsf{prBPP}$ , and suppose we are in the remaining case $\mathsf{EXP}=\mathsf{BPP}$ (which is equivalent to $\mathsf{prEXP}=\mathsf{prBPP}$ ). We get that $\mathsf{prZPEXP}\neq\mathsf{prEXP}$ . By our aforementioned Karp–Lipton theorem, we obtain that $\mathsf{ZPE}/_{n}\nsubseteq\mathsf{SIZE}[n^{k}]$ for all $k$ . Again, using the hardness-vs-randomness framework, this allows us to obtain an infinitely-often secure PRG with sub-polynomial seed length that is computable probabilistically with zero error using a small amount of advice. Proceeding similarly to previous proofs, this yields weak coding for $\mathsf{zKt}$ , as desired.

Complexity Separations and Meta-Complexity.

We first describe the proof of Theorem 5. As mentioned in Section 1.2.4, it was shown in [1] that $\mathsf{EXP}=\mathsf{BPP}$ if and only if $\mathsf{Gap}$ - $\mathsf{MKtP}\in\mathsf{prBPP}$ . The original proof relied on the fact that $\mathsf{EXP}$ admits instance checkers [4], which are not available for $\mathsf{NEXP}$ . Here, we provide an alternative proof that does not use instance checkers.

For the direction that $\mathsf{NEXP}=\mathsf{BPP}$ implies $\mathsf{Gap}$ - $\mathsf{MnKtP}\in\mathsf{prBPP}$ , it is not hard to see that $\mathsf{MnKtP}\in\mathsf{PSPACE}^{\mathsf{NEXP}}$ , where the queries to the $\mathsf{NEXP}$ oracle are of polynomial size. It is then not difficult to show that the desired inclusion follows from $\mathsf{NEXP}=\mathsf{BPP}$ . Indeed, we get the stronger conclusion that $\mathsf{MnKtP}\in\mathsf{BPP}$ .

For the other direction, assume $\mathsf{NEXP}\neq\mathsf{BPP}$ . Then, as shown in previous paragraphs, we obtain an infinitely-often secure PRG that is computable non-deterministically with a small amount of advice. Now suppose, for the sake of contradiction, that $\mathsf{Gap}$ - $\mathsf{MnKtP}\in\mathsf{prBPP}$ . In that case, an efficient algorithm solving $\mathsf{Gap}$ - $\mathsf{MnKtP}$ could be used to break the security of the aforementioned PRG. This is because every output of such a PRG has small $\mathsf{nKt}$ -complexity, while a uniformly random string has high $\mathsf{nKt}$ -complexity.

The proof of Theorem 6 for $\mathsf{Gap}$ - $\mathsf{MzKtP}$ can be shown similarly, using a PRG that is computable probabilistically with zero error using a small advice. Such a PRG can be obtained under the assumption that $\mathsf{prZPEXP}\neq\mathsf{prBPP}$ , as described in previous paragraphs.

Finally, for our unconditional lower bound in Theorem 7, a natural approach is to try to adapt the lower bound for $\mathsf{rKt}$ in the two-sided error setting from [40] to the zero-error setting. The proof makes crucial use of techniques from pseudorandomness and of the properties of the reconstruction procedure of different PRGs. In order to adapt the original argument to the zero-error setting, it is necessary to obtain zero-error reconstruction routines for the corresponding PRGs. This, however, seems to be out of reach using current techniques (see [29] for related results).

Instead, we show that if $\mathsf{Gap}$ - $\mathsf{MzKtP}$ can be solved by a zero-error randomized algorithm in quasi-polynomial time, then, using the easy witness method introduced by [24], one can approximately “collapse” $\mathsf{rKt}$ and $\mathsf{zKt}$ (see [20, Lemma 40]). This, in particular, implies that $\mathsf{Gap}$ - $\mathsf{MrKtP}$ can also be solved in quasi-polynomial time by a randomized algorithm. Using the known unconditional lower bound for $\mathsf{Gap}$ - $\mathsf{MrKtP}$ established in [40], this leads to a contradiction.

Remainder of the paper.

We provide the necessary background in Section 2. In Section 3, we establish the equivalence between complexity lower bounds and coding for $\mathsf{Kt}$ complexity (Theorem 1), and in Section 4 we extend these results to $\mathsf{nKt}$ (Theorem 3). Due to space limitations, we omit the proofs of the corresponding equivalence for $\mathsf{zKt}$ (Theorem 4), as well as the results on meta-complexity (Theorems 5, 6, and 7). Full details are available in the full version [20].

2 Preliminaries

2.1 Time-Bounded Kolmogorov Complexity

Fix a time-efficient universal Turing machine $U$ . For convenience of the reader, we collect below the main notions of time-bounded Kolmogorov complexity considered in this work.

Definition 8 ( $\mathsf{Kt}$ [28]).

For a string $x\in\{0,1\}^{*}$ and an oracle $\mathcal{O}\subseteq\{0,1\}^{*}$ , we let

\mathsf{Kt}^{\mathcal{O}}(x)\triangleq\min_{p\in\{0,1\}^{*},\;t\in\mathbb{N}}% \Big\{|p|+\lceil\log t\rceil\colon U^{\mathcal{O},t}(p)=x\Big\}.

The notation $U^{\mathcal{O},t}(p)$ denotes that $U$ computes for at most $t$ steps. In the absence of $\mathcal{O}$ , we simply write $\mathsf{Kt}(x)$ .

Definition 9 ( $\mathsf{rKt}$ [40]).

For a string $x\in\{0,1\}^{*}$ , we let

\mathsf{rKt}(x)\triangleq\min_{p\in\{0,1\}^{*},\;t\in\mathbb{N}}\Big\{|p|+% \lceil\log t\rceil\colon\operatorname*{{\bf Pr}}_{r}[U^{t}(p,r)=x]\geq 2/3\Big\}.

Next, we define zero-error and nondeterministic analogues of these measures.

Definition 10 ( $\mathsf{zKt}$ ).

For a string $x\in\{0,1\}^{*}$ , we let

\mathsf{zKt}(x)\triangleq\min_{p\in\{0,1\}^{*},\,t\in\mathbb{N}}\left\{|p|+% \lceil\log t\rceil\,\,\middle|\,\,\operatorname*{{\bf Pr}}_{r}[U^{t}(p,r)=x]% \geq 2/3\nobreak\ \text{and}\nobreak\ \forall r,\nobreak\ U^{t}(p,r)\in\{x,% \bot\}\right\}.

Definition 11 ( $\mathsf{nKt}$ ).

For $x\in\{0,1\}^{*}$ , we let

\mathsf{nKt}(x)\triangleq\min_{p\in\{0,1\}^{*},\,t\in\mathbb{N}}\left\{|p|+% \lceil\log t\rceil\,\,\middle|\,\,\exists w,U^{t}(p,w)=x\nobreak\ \text{and}% \nobreak\ \forall w,\nobreak\ U^{t}(p,w)\in\{x,\bot\}\right\}.

Note that, for every $x\in\{0,1\}^{*}$ , we have $\mathsf{nKt}(x)\leq\mathsf{zKt}(x)\leq\mathsf{Kt}(x)$ and $\mathsf{rKt}(x)\leq\mathsf{zKt}(x)\leq\mathsf{Kt}(x)$ . The relation between $\mathsf{rKt}(x)$ and $\mathsf{nKt}(x)$ is unclear. For an overview of probabilistic notions of Kolmogorov complexity and their applications, we refer to [36].

2.2 Pseudorandomness

For a finite set $A$ , we write $x\sim A$ to denote that $x$ is uniformly distributed over $A$ .

Let $\mathcal{D}_{n}$ be a distribution supported over $\{0,1\}^{n}$ . Let $\varepsilon\in[0,1]$ . Finally, let $f\colon\{0,1\}^{n}\to\{0,1\}$ . We say that $\mathcal{D}_{n}$ $\varepsilon$ -fools $f$ if

\Big|\operatorname*{{\bf Pr}}_{x\sim\mathcal{D}_{n}}[f(x)=1]-\operatorname*{{% \bf Pr}}_{x\sim\{0,1\}^{n}}[f(x)=1]\Big|\leq\varepsilon.

For a function $H\colon\{0,1\}^{\ell}\to\{0,1\}^{m}$ , we write $H(-)$ to denote the distribution induced by $H(y)$ for $y\sim\{0,1\}^{\ell}$ .

Theorem 12 ([5]).

For every $\varepsilon>0$ and $b\in\mathbb{N}$ , there exist a polynomial time computable function $F:\{0,1\}^{*}\times\{0,1\}^{*}\to\{0,1\}^{*}$ , $\delta<\varepsilon$ and $c\in\mathbb{N}$ such that the following holds.

F\colon\{0,1\}^{2^{n^{\delta}}}\times\{0,1\}^{n^{\varepsilon}}\to\{0,1\}^{n^{b% }},

and if $T$ is the truth table of a Boolean function on $n^{\delta}$ variables that has circuit complexity at least $n^{c\delta}$ , then the generator $G^{T}(-)\triangleq F(T,-)$ $(n^{-b})$ -fool every circuit of size at most $n^{b}$ .

Theorem 13 ([23, 43]).

Assume $\mathsf{PSPACE}\neq\mathsf{BPP}$ . Then for every $\varepsilon>0$ and $b\in\mathbb{N}$ , there is a sequence $\{G_{n}\}_{n\in\mathbb{N}}$ , where $G_{n}\colon\{0,1\}^{n^{\varepsilon}}\to\{0,1\}^{n^{b}}$ is computable in time $2^{O(n^{\varepsilon})}$ , such that the following holds. For every distribution family $\{\mathcal{C}_{n}\}_{n\in\mathbb{N}}$ of Boolean circuits samplable in time $n^{b}$ , there are infinitely many $n\in\mathbb{N}$ such that with probability at least $1-n^{-b}$ over $C$ sampled from $\mathcal{C}_{n}$ , $G_{n}$ $(n^{-b})$ -fools $C$ .

2.3 Complexity Theory and Diagonalization Against Advice

For the definition of standard notions, such as complexity classes with advice and promise classes, we refer to a textbook in complexity theory.

The following simple diagonalization lemma will be sufficient for our purposes.

Lemma 14.

Let $a(n),b(n),c(n),s(n)$ be time-constructible functions satisfying the following properties:

1.

$b^{2}(n)\cdot 2^{3c(n)}\cdot s^{3}(n)=o(a(n))$ ,
2.

$c(n)+\log s(n)<2^{n}$ ,
3.

$s(n)=\omega(1)$ ,
4.

$b(n)=\Omega(n)$ .

Then we have $\mathsf{DTIME}[a(n)]\nsubseteq\mathsf{i.o.DTIME}[b(n)]/_{c(n)}$ .

Proof.

We define a language as follows. For input length $n$ , define $l(n)=\lfloor\log(s(n)\cdot 2^{c(n)})\rfloor+1$ . Item 2 guarantees that $l(n)\leq 2^{n}$ . We construct the length- $l(n)$ prefix of truth tables of the first $s(n)$ Turing machines with all possible length- $c(n)$ advice strings running in time $b(n)$ . There are at most $s(n)\cdot 2^{c(n)}$ such prefixes, and since $2^{l(n)}>s(n)\cdot 2^{c(n)}$ , we can enumerate over all length- $l(n)$ strings, and find the first string $p$ outside this list. We then define the truth table of this language on input length $n$ as $p0^{2^{n}-l(n)}$ .

The first enumeration and simulation step takes time $s(n)\cdot 2^{c(n)}\cdot l(n)\cdot b(n)\cdot\log b(n)$ . Using a naive search over all $l(n)$ -bit strings, finding $p$ takes time at most $s(n)\cdot 2^{c(n)}\cdot l(n)\cdot 2^{l(n)}$ . By Item 1 and Item 4, this language is decidable in time $a(n)$ . However, by our construction and Item 3, any Turing machine running in time $b(n)$ fails to decide this language with any length- $c(n)$ advice string for all large enough $n$ . $\hfill\blacktriangleleft$

Recall that $\mathsf{EE}\triangleq\mathsf{DTIME}[2^{2^{O(n)}}]$ denotes the class of languages that can be decided in double exponential time, $\mathsf{E}\triangleq\mathsf{DTIME}[2^{O(n)}]$ denotes the class of languages that can be decided in single exponential time, and $\mathsf{EXP}\triangleq\mathsf{DTIME}[2^{n^{O(1)}}]$ .

Corollary 15.

For any fixed $k\in\mathbb{N}$ and time-constructible $s(n)=\omega(1)$ , we have $\mathsf{EE}\nsubseteq\mathsf{i.o.DTIME}[2^{2^{kn}}]/_{2^{n}-s(n)}$ .

Corollary 16.

For any fixed $k\in\mathbb{N}$ , $\mathsf{EXP}\nsubseteq\mathsf{i.o.SIZE}[n^{k}]$ .

For a language $L\subseteq\{0,1\}^{*}$ , we let $\mathsf{tt}(L^{=n})\in\{0,1\}^{2^{n}}$ denote the string representing the truth table of $L$ on inputs of length $n$ .

3 Coding for Deterministic Time-Bounded Kolmogorov Complexity

3.1 Equivalence Between Coding for $\mathsf{Kt}$ and $\mathsf{EXP}\neq\mathsf{BPP}$

Theorem 1. [Restated, see original statement.]

The following statements are equivalent.

1.

$\mathsf{EXP}\neq\mathsf{BPP}$ .
2.

(Weak coding for $\mathsf{Kt}$ .) For any $\varepsilon>0$ and any polynomial-time samplable distribution family $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ , there are infinitely many $n\in\mathbb{N}$ such that for all $x\in\mathsf{Support}(\mathcal{D}_{n})$ ,

$\mathsf{Kt}(x)\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n\right)^{% \varepsilon}.$
3.

(Non-trivial coding for $\mathsf{Kt}$ .) There exists a constant $c>0$ such that the following holds. Let $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ be a polynomial-time samplable distribution family, where each $\mathcal{D}_{n}$ is supported over $\{0,1\}^{n}$ , satisfying that there exists a sequence $\{x_{n}\}_{n\in\mathbb{N}}$ such that $\mathcal{D}_{n}(x_{n})\geq 1-n^{-c}$ for every $n$ . Then for infinitely many $n$ , we have

$\mathsf{Kt}(x_{n})\leq n-\omega(\log n).$

Proof.

We show the following implications.
(Item 2 $\Longrightarrow$ Item 3). This holds trivially.
(Item 3 $\Longrightarrow$ Item 1). This is shown by Lemma 17, stated and proved in Section 3.1.1.
(Item 1 $\Longrightarrow$ Item 2). This follows from Lemma 19, stated and proved in Section 3.1.2. $\hfill\blacktriangleleft$

3.1.1 $\mathsf{EXP}\neq\mathsf{BPP}$ from Non-Trivial Coding for $\mathsf{Kt}$

Lemma 17.

(Item 3 $\Rightarrow$ Item 1 in Theorem 1). If non-trivial coding for $\mathsf{Kt}$ is true, then $\mathsf{EXP}\neq\mathsf{BPP}$ .

Proof.

For the sake of contradiction, suppose $\mathsf{EXP}=\mathsf{BPP}$ . By a simple padding argument, this implies $\mathsf{EE}\subseteq\mathsf{BPE}$ . Then it suffices to show the existence of a language $L_{\mathsf{hard}}\in\mathsf{EE}$ such that $L_{\mathsf{hard}}\not\in\mathsf{BPE}$ .

We first show the following claim.

Claim 18.

If non-trivial coding for $\mathsf{Kt}$ is true, then for every $L\in\mathsf{BPE}$ , there are infinitely many $n$ such that $\mathsf{Kt}(\mathsf{tt}(L^{=n}))\leq 2^{n}-\omega(n)$ .

Proof of Claim 18.

Let $c>0$ be the constant in the non-trivial coding theorem (Item 3 of Theorem 1).

Fix $L\in\mathsf{BPE}$ . Let $M$ be a $2^{O(cn)}$ -time probabilistic Turing machine that computes $L$ on each input of length $n$ with error $\leq 2^{-n-cn}$ . Such a machine can be obtained by using error reduction techniques.

Consider the distribution family $\mathcal{D}\triangleq\{\mathcal{D}_{N}\}$ where each $\mathcal{D}_{N}$ is defined by the following sampling procedure:

On input $1^{N}$ , let $n\triangleq\lceil\log N\rceil$ . Let $S$ be the ordered set consisting of the lexicographically first $N$ elements of $\{0,1\}^{n}$ . For each $x\in S$ compute $b_{x}\triangleq M(x)$ . Finally, output $\displaystyle\mathrel{{{\circ}}}_{x\in S}b_{x}$ , i.e., the concatenation of these bits.

Note that since $M$ has exponentially small error for each input, by a union bound, we get that for every $N\in\mathbb{N}$ , with probability at least $1-2^{-cn}$ , $\mathcal{D}_{N}$ outputs the $N$ -bit prefix of the truth table given by $L^{=n}$ , i.e., $\mathsf{tt}(L^{=n})_{[1:N]}$ , where $n=\lceil\log N\rceil$ . Also note that $\mathcal{D}$ is polynomial-time samplable.

By applying non-trivial coding for $\mathsf{Kt}$ to $\mathcal{D}$ , it follows that there are infinitely many $N$ such that, for $n\triangleq\lceil\log N\rceil$ ,

\mathsf{Kt}\left(\mathsf{tt}(L^{=n})_{[1:N]}\right)\leq N-\omega(\log N)\leq N% -\omega(n).

Fix any $N$ such that the above holds, and let $(p,t)\in\{0,1\}^{*}\times\mathbb{N}$ be such that $|p|+\log t\leq N-\omega(n)$ and $U(p)$ outputs $\mathsf{tt}(L^{=n})_{[1:N]}$ within $t$ steps. Consider the following procedure for generating $\mathsf{tt}(L^{=n})$ .

Given $(p,\mathsf{suffix}\triangleq\mathsf{tt}(L^{=n})_{[N+1,2^{n}]})$ , we first run $U(p)$ to obtain $\mathsf{prefix}\triangleq\mathsf{tt}(L^{=n})_{[1:N]}$ and output $\mathsf{prefix}\mathrel{{{\circ}}}\mathsf{suffix}$ .

It is easy to see that the above procedure runs in time $t\cdot 2^{O(n)}$ . This implies that

	$\displaystyle\mathsf{Kt}(\mathsf{tt}(L^{=n}))$	$\displaystyle\leq\|p\|+(2^{n}-N)+O(n)+\log\left(t\cdot 2^{O(n)}\right)$
		$\displaystyle\leq 2^{n}-\omega(n).$

This completes the proof of Claim 18. $\hfill\vartriangleleft$

We define the language $L_{\mathsf{hard}}$ as follows.

On input $x\in\{0,1\}^{n}$ , we first compute a string $T\in\{0,1\}^{2^{n}}$ such that $\mathsf{Kt}(T)>2^{n}-1$ , as follows. We enumerate all pairs $(p,t)\in\{0,1\}^{*}\times\mathbb{N}$ such that $|p|+\lceil\log t\rceil\leq 2^{n}-1$ and run $U(p)$ for at most $t$ steps. This gives all the strings whose $\mathsf{Kt}$ -complexity are at most $2^{n}-1$ . We then let $T$ be the lexicographically first $2^{n}$ -bit string that is not in the list. Finally, we output the $x$ -th bit of $T$ .

It is easy to see that $L_{\mathsf{hard}}\in\mathsf{EE}$ . Also, by construction, we have that for all $n$ , $\mathsf{Kt}(\mathsf{tt}(L_{\mathsf{hard}}^{=n}))>2^{n}-1$ . It follows from Claim 18 that $L_{\mathsf{hard}}\not\in\mathsf{BPE}$ . $\hfill\blacktriangleleft$

3.1.2 Weak Coding for $\mathsf{Kt}$ from $\mathsf{EXP}\neq\mathsf{BPP}$

Lemma 19.

(Item 1 $\Rightarrow$ Item 2 in Theorem 1). If $\mathsf{EXP}\neq\mathsf{BPP}$ , then weak coding for $\mathsf{Kt}$ is true.

We first show the following technical lemma.

Lemma 20.

If $\mathsf{EXP}\neq\mathsf{BPP}$ , then for every $\varepsilon>0$ and $b\in\mathbb{N}$ , there is a sequence $\{G_{n}\}_{n\in\mathbb{N}}$ , where $G_{n}\colon\{0,1\}^{n^{\varepsilon}}\to\{0,1\}^{n^{b}}$ is computable in time $2^{O(n^{\varepsilon})}$ , such that the following holds. For every distribution family $\{\mathcal{C}_{n}\}_{n\in\mathbb{N}}$ of Boolean circuits samplable in time $n^{b}$ , there are infinitely many $n\in\mathbb{N}$ such that with probability at least $1-n^{-b}$ over $C$ sampled from $\mathcal{C}_{n}$ , $G_{n}$ $(n^{-b})$ -fools $C$ .

Proof.

Assume $\mathsf{EXP}\neq\mathsf{BPP}$ . We consider two cases and show that the desired conclusion holds in each one of those cases.

Case 1: $\mathsf{PSPACE}\not\subseteq\mathsf{BPP}$ .

The desired pseudorandom generator follows directly from Theorem 13.

Case 2: $\mathsf{PSPACE}\subseteq\mathsf{BPP}$ .

Since we assume $\mathsf{EXP}\not\subseteq\mathsf{BPP}$ , we have $\mathsf{EXP}\neq\mathsf{PSPACE}$ in this case. Recall that if $\mathsf{EXP}\subseteq\mathsf{SIZE}[\mathsf{poly}]$ then $\mathsf{EXP}=\mathsf{PSPACE}$ [25]. Therefore, we have $\mathsf{EXP}\nsubseteq\mathsf{SIZE}[\mathsf{poly}]$ , which further implies $\mathsf{E}\not\subseteq\mathsf{SIZE}[\mathsf{poly}]$ . Let $L\in\mathsf{E}$ be a language that is not computable by any polynomial-size circuit.

Consider any $0<\varepsilon<1$ and $b\in\mathbb{N}$ . Let $F$ , $\delta<\varepsilon$ and $c\in\mathbb{N}$ be as provided by Theorem 12. By the property of $F$ and the hardness of the language $L$ , we have that, for infinitely many $n$ , the generator $G_{n}\colon\{0,1\}^{n^{\varepsilon}}\to\{0,1\}^{n^{b}}$ , defined as

G_{n}(-)\triangleq F\left(\mathsf{tt}(L^{=n^{\delta}}),-\right),

$(n^{-b})$ -fools circuits of size at most $n^{b}$ . Note that since $L\in\mathsf{E}$ , $\mathsf{tt}(L^{=n^{\delta}})$ can be obtained in time $2^{O(n^{\delta})}$ . Also, $F$ is polynomial-time computable. It follows that each $G_{n}$ can be computed in time $2^{O(n^{\varepsilon})}$ . Finally, note that the above also yields the desired conclusion. $\hfill\blacktriangleleft$

We are now ready to show Lemma 19.

Proof of Lemma 19.

Assume $\mathsf{EXP}\neq\mathsf{BPP}$ . The main idea is to use the pseudorandom generator $G$ in Lemma 20 to “hit” any string $x$ that is sampled with probability at least $1/\mathsf{poly}(n)$ . That is, there is a seed $z\in\{0,1\}^{n^{\varepsilon}}$ such that $A(G(z))=x$ . Then $x$ can be encoded using the short seed $z$ . Details follow.

Let $\varepsilon>0$ and $\{\mathcal{D}_{n}\}$ be a distribution family that admits a sampler $A$ that, on input $1^{n}$ , runs in time at most $n^{c}$ , for some constant $c\geq 1$ .

Let $\{G_{n}\colon\{0,1\}^{n^{\varepsilon/2}}\to\{0,1\}^{n^{b}}\}$ be the sequence of generators in Theorem 13, where $b>c/\varepsilon$ is a constant specified later.

Consider the following distribution $\{\mathcal{C}_{n}\}$ of circuits:

On input $1^{n}$ , we run $A(1^{n})$ to obtain a string $x$ . We then construct the circuit $C_{x}$ such that $C_{x}(r)=1$ if and only if $A(1^{n};r)=x$ . Finally, we output $C_{x}$ .

First of all, note that by letting $b$ be a sufficiently large constant, we get that $\{\mathcal{C}_{n}\}$ is samplable in time $n^{b}$ . Then by Theorem 13 and the security of $\{G_{n}\}$ , there are infinitely many $n$ such that

\operatorname*{{\bf Pr}}_{C\sim\mathcal{C}_{n}}\left[\textnormal{$G_{n}$ $(n^{% -b})$-fools $C$}\right]\geq 1-n^{-b}.

(1)

Now fix any large enough $n$ such that Equation 1 holds and consider any $x$ in the support of $D_{n}$ . Suppose $\mathcal{D}_{n}(x)<n^{-c/\varepsilon}$ . Then we have

\mathsf{Kt}(x)\leq 2\cdot n^{c}\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n% \right)^{\varepsilon},

as desired.

Suppose $\mathcal{D}_{n}(x)\geq n^{-c/\varepsilon}$ . Then by construction, we have that $\mathcal{C}_{n}$ samples $C_{x}$ with probability at least $n^{-c/\varepsilon}>n^{-b}$ . It follows from Equation 1 that $G_{n}$ $(n^{-b})$ -fools $C_{x}$ ; this is because otherwise the probability that $G_{n}$ fails to be pseudorandom would be greater than $n^{-b}$ . In particular, this means

	$\displaystyle\operatorname*{{\bf Pr}}_{z\sim\{0,1\}^{n^{\varepsilon/2}}}\left[% C_{x}(G_{n}(z))=1\right]$	$\displaystyle\geq\operatorname*{{\bf Pr}}_{r\sim\{0,1\}^{n^{b}}}\left[C_{x}(r)% =1\right]-n^{-b}$
		$\displaystyle\geq n^{-c/\varepsilon}-n^{-b}>0.$

It follows that there exists some $z\in\{0,1\}^{n^{\varepsilon/2}}$ such that $A(1^{n};G_{n}(z))=x$ . From here, it is easy to show that $\mathsf{Kt}(x)\leq n^{\varepsilon}$ , as desired. $\hfill\blacktriangleleft$

3.2 Stronger Lower Bounds from Near-Optimal Coding for $\mathsf{Kt}$

We say that near-optimal coding for $\mathsf{Kt}$ holds if for every polynomial-time sampler $A(1^{n})$ and for every string $x\in\{0,1\}^{n}$ , if $x$ has probability $\geq\delta$ under $A(1^{n})$ then $\mathsf{Kt}(x)=O(\log(1/\delta)+\log n)$ .

Theorem 21.

Suppose that near-optimal coding for $\mathsf{Kt}$ holds. Then, for every $c\geq 1$ there is $k\geq 1$ and a language $L\in\mathsf{DTIME}[2^{kn}]$ such that $L\notin\mathsf{i.o.}\mathsf{BPTIME}[2^{cn}]$ .

Proof.

Fix a constant $c\geq 1$ . We define a sampler $A(1^{N})$ with $N\triangleq 2^{n}$ that randomly selects one of the first $\alpha(N)\triangleq\log\log N$ randomized Turing machines, runs it for $2^{2cn}$ steps on every string of length $n$ , and outputs the corresponding truth table. We also assume that $A(1^{N})$ boosts the success probability of the machine on a given input string by simulating it $n^{2}$ times and taking a majority vote, meaning that once a machine with bounded acceptance probabilities is selected, the corresponding truth table is produced with probability at least $9/10$ .

Note that for every language $L^{\prime}\in\mathsf{BPTIME}[2^{cn}]$ and for each large enough $n$ , the truth table of $L^{\prime}$ on inputs of length $n$ is output by $A(1^{N})$ with probability at least $\delta\triangleq(9/10)\cdot(1/\log\log N)=\Omega(1/\log n)$ . Consequently, by the near-optimal coding assumption, every truth table in $\mathsf{BPTIME}[2^{cn}]$ (a string of length $N=2^{n}$ ) has $\mathsf{Kt}$ complexity at most $O(\log(1/\delta)+\log N)\leq c_{1}\cdot n$ , for a large enough constant $c_{1}$ .

Finally, we can define a hard language $L\in\mathsf{DTIME}[2^{kn}]$ as follows. On an input string of length $n$ , we find by diagonalization a string of length $2^{n}$ of $\mathsf{Kt}$ complexity $\geq c_{2}n$ , for $c_{2}>c_{1}$ , and compute according to the truth table encoded by this string. The latter can be done by exhaustive search in deterministic time $2^{kn}$ , for a large enough positive integer $k>c_{2}$ . By the previous paragraph, we obtain that $L\notin\mathsf{BPTIME}[2^{cn}]$ , which completes the proof. $\hfill\blacktriangleleft$

We note that the elementary proof given above strengthens and simplifies [26, Theorem 5.3.4].

4 Coding for Non-Deterministic Time-Bounded Kolmogorov Complexity

4.1 Equivalence Between Coding for $\mathsf{nKt}$ and $\mathsf{NEXP}\neq\mathsf{BPP}$

Theorem 22.

The following statements are equivalent.

1.

$\mathsf{NEXP}\neq\mathsf{BPP}$ .
2.

(Weak coding for $\mathsf{nKt}$ ) For any $\varepsilon>0$ and any polynomial-time samplable distribution family $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ , there are infinitely many $n\in\mathbb{N}$ such that for all $x\in\mathsf{Support}(\mathcal{D}_{n})$ ,

$\mathsf{nKt}(x)\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n\right)^{% \varepsilon}.$
3.

(Non-trivial coding for $\mathsf{nKt}$ .) There exists a constant $c>0$ such that the following holds. Let $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ be a polynomial-time samplable distribution family, where each $\mathcal{D}_{n}$ is supported over $\{0,1\}^{n}$ , satisfying that there exists a sequence $\{x_{n}\}_{n\in\mathbb{N}}$ such that $\mathcal{D}_{n}(x_{n})\geq 1-n^{-c}$ for every $n$ . Then for infinitely many $n$ , we have

$\mathsf{nKt}(x_{n})\leq n-\omega(\log n).$

Proof.

We establish the following implications:
(Item 2 $\Longrightarrow$ Item 3). This follows immediately.
(Item 3 $\Longrightarrow$ Item 1). This is shown by Lemma 23, which is stated and proved in Section 4.1.1.
(Item 1 $\Longrightarrow$ Item 2). This follows from Lemma 26, which is stated and proved in Section 4.1.2. $\hfill\blacktriangleleft$

4.1.1 $\mathsf{NEXP}\neq\mathsf{BPP}$ from Non-Trivial Coding for $\mathsf{nKt}$

Lemma 23.

(Item 3 $\Rightarrow$ Item 1 in Theorem 22). If non-trivial coding for $\mathsf{nKt}$ is true, then $\mathsf{NEXP}\neq\mathsf{BPP}$ .

Proof.

We first show the following two claims.

Claim 24.

If non-trivial coding for $\mathsf{nKt}$ is true, then for every $L\in\mathsf{BPE}$ , there are infinitely many $n$ such that $\mathsf{nKt}(\mathsf{tt}(L^{=n}))\leq 2^{n}-\omega(n)$ .

Proof Sketch of Claim 24.

The proof can be easily adapted from that of Claim 18, by replacing the use of non-trivial coding for $\mathsf{Kt}$ with that for $\mathsf{nKt}$ . $\hfill\vartriangleleft$

Claim 25.

If non-trivial coding for $\mathsf{nKt}$ is true, then

\mathsf{BPE}\subseteq\mathsf{i.o.NTIME}\left[2^{2^{n}-\omega(n)}\right]/_{2^{n% }-\omega(n)}.

Proof of Claim 25.

Fix $L\in\mathsf{BPE}$ . First of all, by Claim 24, we have that there are infinitely many $n$ such that $\mathsf{nKt}(\mathsf{tt}(L^{=n}))\leq 2^{n}-\omega(n)$ . This means for infinitely many $n$ , there exist a program $p$ of size at most $2^{n}-\omega(n)$ such that for $t\triangleq 2^{2^{n}-\omega(n)}$ ,

$\blacksquare$

$\exists w\in\{0,1\}^{t}$ , $U(p,w)$ outputs $\mathsf{tt}(L^{=n})$ within $t$ steps, and
$\blacksquare$

$\forall w\in\{0,1\}^{t}$ , $U(p,w)$ outputs $\mathsf{tt}(L^{=n})$ or $\bot$ within $t$ steps

It is easy to see that for any $n$ such that the above holds, given $p$ as an advice, $L$ on input length $n$ can be solved non-deterministically in time $2^{2^{n}-\omega(n)}$ , by guessing $w\in\{0,1\}^{t}$ and trying to use $p$ to generate $\mathsf{tt}(L^{=n})$ . $\hfill\vartriangleleft$ We are now ready to show the lemma. Suppose

\mathsf{NEXP}=\mathsf{BPP}.

(2)

Note that by the existence of languages that are $\mathsf{NE}$ -complete under linear-time reductions, the above implies that there exists some $k>0$ such that

\mathsf{NE}\subseteq\mathsf{BPTIME}[n^{k}].

(3)

Next, we aim to derive a contradiction. By Equation 2 and padding, we have

\mathsf{EE}\subseteq\mathsf{BPE}.

(4)

By Claim 25, we get

\mathsf{BPE}\subseteq\mathsf{i.o.NTIME}\left[2^{2^{n}}\right]/_{2^{n}-\omega(n% )}.

(5)

Now by using Equation 3 and a standard padding argument that incorporates the advice as an extra input string, we get that there exists some $k^{\prime}>0$ such that

\mathsf{NTIME}\left[2^{2^{n}}\right]/_{2^{n}-\omega(n)}\subseteq\mathsf{BPTIME% }\left[2^{k^{\prime}n}\right]/_{2^{n}-\omega(n)}.

(6)

Finally, by deterministic simulation of randomized algorithms, we get that there exists some $k>0$ such that

\mathsf{BPTIME}\left[2^{k^{\prime}n}\right]/_{2^{n}-\omega(n)}\subseteq\mathsf% {DTIME}\left[2^{2^{kn}}\right]/_{2^{n}-\omega(n)}.

(7)

Equations 4, 5, 6, and 7 yield the existence of some $k>0$ such that

\mathsf{EE}\subseteq\mathsf{i.o.DTIME}\left[2^{2^{kn}}\right]/_{2^{n}-\omega(n)}

However, the above contradicts Corollary 15. $\hfill\blacktriangleleft$

4.1.2 Weak Coding for $\mathsf{nKt}$ from $\mathsf{NEXP}\neq\mathsf{BPP}$

Lemma 26.

(Item 1 $\Rightarrow$ Item 2 in Theorem 22). If $\mathsf{NEXP}\neq\mathsf{BPP}$ , then weak coding for $\mathsf{nKt}$ is true.

We rely on the following result, which is analogous to Lemma 20 but for the case of $\mathsf{NEXP}\neq\mathsf{BPP}$ .

Lemma 27.

If $\mathsf{NEXP}\neq\mathsf{BPP}$ , then for every $\varepsilon>0$ and $b\in\mathbb{N}$ , there is a sequence $\{G_{n}\}_{n\in\mathbb{N}}$ , where $G_{n}\colon\{0,1\}^{n^{\varepsilon}}\to\{0,1\}^{n^{b}}$ , such that the following holds. For every distribution family $\{\mathcal{C}_{n}\}_{n\in\mathbb{N}}$ of Boolean circuits samplable in time $n^{b}$ , there are infinitely many $n\in\mathbb{N}$ such that with probability at least $1-n^{-b}$ over $C$ sampled from $\mathcal{C}_{n}$ , $G_{n}$ $(n^{-b})$ -fools $C$ . Moreover, each $G_{n}$ can be computed non-deterministically with advice in the following sense: There exists a deterministic Turing machine $M$ and a sequence of advice strings ${a_{n}\in\{0,1\}^{n^{\varepsilon}}}$ such that, given $z\in\{0,1\}^{n^{\varepsilon}}$ and $w\in\{0,1\}^{2^{n^{\varepsilon}}}$ , $M(z,w;a_{n})$ runs in time $2^{O(n^{\varepsilon})}$ . Also, for every $z\in\{0,1\}^{n^{\varepsilon}}$ , the following hold:

$\blacksquare$

There exists $w\in\{0,1\}^{2^{n^{\varepsilon}}}$ such that $M(z,w;a_{n})=G_{n}(z)$ .
$\blacksquare$

For all $w\in\{0,1\}^{2^{n^{\varepsilon}}}$ , $M(z,w;a_{n})\in\{G_{n}(z),\bot\}$ .

Proof.

The proof is similar to that of Lemma 20 but requires some crucial observations on the efficiency of computing the pseudorandom generator in the non-deterministic setting.

Assume $\mathsf{NEXP}\neq\mathsf{BPP}$ . We consider two cases below.

Case 1: $\mathsf{PSPACE}\not\subseteq\mathsf{BPP}$ .

The desired pseudorandom generator follows directly from Theorem 13.

Case 2: $\mathsf{PSPACE}\subseteq\mathsf{BPP}$ .

By the assumption that $\mathsf{NEXP}\neq\mathsf{BPP}$ , we get that $\mathsf{NEXP}\neq\mathsf{PSPACE}$ in this case. Then, by [22], $\mathsf{NEXP}\subseteq\mathsf{SIZE}[\mathsf{poly}]$ implies $\mathsf{NEXP}=\mathsf{MA}=\mathsf{PSPACE}$ . Therefore, we obtain $\mathsf{NEXP}\nsubseteq\mathsf{SIZE}[\mathsf{poly}]$ in this case.

Analogous to the proof of Lemma 20, given that $\mathsf{NEXP}\nsubseteq\mathsf{SIZE}[\mathsf{poly}]$ , we have a language $L\in\mathsf{NE}$ that is not computable by any polynomial-size circuit. Then for every $\varepsilon>0$ and $b\in\mathbb{N}$ , we get that the generator $G_{n}\colon\{0,1\}^{n^{\varepsilon}}\to\{0,1\}^{b}$ , defined as $G_{n}(-)\triangleq F\left(\mathsf{tt}(L^{=n^{\delta}}),-\right)$ , where $F$ and $\delta>0$ are as provided by Theorem 12, fools circuits of size at most $n^{b}$ , for infinitely many $n$ .

To show that each $G_{n}$ can be computed non-deterministically with a small advice, it suffices to generate $\mathsf{tt}(L^{=n^{\delta}})$ in non-deterministic time $2^{O(n^{\delta})}$ with $n^{\delta}$ bits of advice. This can be done, as observed in [22, Lemma 1]. $\hfill\blacktriangleleft$

We now show Lemma 26.

Proof Sketch of Lemma 26.

If $\mathsf{NEXP}\neq\mathsf{BPP}$ , then by Lemma 27, we have an infinitely-often secure pseudorandom generator that is computable non-deterministically with a small advice string. Using an argument similar to the proof of Lemma 19, such a generator can be used to achieve weak coding for $\mathsf{nKt}$ . $\hfill\blacktriangleleft$

4.2 Equivalence Between Coding for $\mathsf{Kt}^{\mathsf{NP}}$ and $\mathsf{EXP}^{\mathsf{NP}}\neq\mathsf{BPP}$

Theorem 28.

The following statements are equivalent.

1.

$\mathsf{EXP^{\mathsf{NP}}}\neq\mathsf{BPP}$ .
2.

(Weak coding for $\mathsf{Kt}^{\mathsf{NP}}$ ) For any $\varepsilon>0$ and any polynomial-time samplable distribution family $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ , there are infinitely many $n\in\mathbb{N}$ such that for all $x\in\mathsf{Support}(\mathcal{D}_{n})$ ,

$\mathsf{Kt}^{\mathsf{NP}}(x)\leq\left(\frac{1}{\mathcal{D}_{n}(x)}\cdot n% \right)^{\varepsilon}.$
3.

(Non-trivial coding for $\mathsf{Kt}^{\mathsf{NP}}$ .) There exists a constant $c>0$ such that the following holds. Let $\{\mathcal{D}_{n}\}_{n\in\mathbb{N}}$ be a polynomial-time samplable distribution family, where each $\mathcal{D}_{n}$ is supported over $\{0,1\}^{n}$ , satisfying that there exists a sequence $\{x_{n}\}_{n\in\mathbb{N}}$ such that $\mathcal{D}_{n}(x_{n})\geq 1-n^{-c}$ for every $n$ . Then for infinitely many $n$ , we have

$\mathsf{Kt}^{\mathsf{NP}}(x_{n})\leq n-\omega(\log n).$

Proof Sketch.

The proof can be easily adapted from that of Theorem 1.

One difference arises in showing that $\mathsf{EXP^{\mathsf{NP}}}\neq\mathsf{BPP}$ implies weak coding for $\mathsf{\mathsf{Kt}^{\mathsf{NP}}}$ . Analogously to Lemma 20, we can show that if $\mathsf{EXP}^{\mathsf{NP}}\neq\mathsf{BPP}$ , then for every $\varepsilon>0$ and $b\in\mathbb{N}$ , there exists an infinitely-often secure pseudorandom generator $G\triangleq\{G_{n}\}_{n\in\mathbb{N}}$ , where each $G_{n}\colon\{0,1\}^{n^{\varepsilon}}\to\{0,1\}^{n^{b}}$ is computable in time $2^{O(n^{\varepsilon})}$ with access to an $\mathsf{NP}$ oracle. Instead of using the Karp–Lipton theorem for $\mathsf{EXP}$ as in the proof of Lemma 20, we use the version for $\mathsf{EXP}^{\mathsf{NP}}$ [8], which states that if $\mathsf{EXP}^{\mathsf{NP}}\subseteq\mathsf{SIZE}[\mathsf{poly}]$ , then $\mathsf{EXP}^{\mathsf{NP}}=\mathsf{PSPACE}$ . $\hfill\blacktriangleleft$

References

[1] Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467–1493, 2006. doi:10.1137/050628994.
[2] Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci., 77(1):14–40, 2011. doi:10.1016/j.jcss.2010.06.004.
[3] Luis Filipe Coelho Antunes and Lance Fortnow. Worst-case running times for average-case algorithms. In Conference on Computational Complexity (CCC), pages 298–303, 2009. doi:10.1109/CCC.2009.12.
[4] László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex., 1:3–40, 1991. doi:10.1007/BF01200056.
[5] László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307–318, 1993. doi:10.1007/BF01275486.
[6] Marshall Ball, Yanyi Liu, Noam Mazor, and Rafael Pass. Kolmogorov comes to cryptomania: On interactive Kolmogorov complexity and key-agreement. In Symposium on Foundations of Computer Science (FOCS), pages 458–483, 2023. doi:10.1109/FOCS57990.2023.00034.
[7] Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional lower bounds against advice. In International Colloquium on Automata, Languages and Programming (ICALP), pages 195–209, 2009. doi:10.1007/978-3-642-02927-1_18.
[8] Harry Buhrman and Steven Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 116–127, 1992. doi:10.1007/3-540-56287-7_99.
[9] Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Conference on Computational Complexity (CCC), pages 10:1–10:24, 2016. doi:10.4230/LIPIcs.CCC.2016.10.
[10] Halley Goldberg and Valentine Kabanets. Improved learning from Kolmogorov complexity. In Computational Complexity Conference (CCC), pages 12:1–12:29, 2023. doi:10.4230/LIPIcs.CCC.2023.12.
[11] Halley Goldberg and Valentine Kabanets. Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM), pages 51:1–51:19, 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.51.
[12] Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov complexity with applications to average-case complexity. In Computational Complexity Conference (CCC), pages 16:1–16:60, 2022. doi:10.4230/LIPIcs.CCC.2022.16.
[13] Shuichi Hirahara. Average-case hardness of NP from exponential worst-case hardness assumptions. In Symposium on Theory of Computing (STOC), pages 292–302, 2021. doi:10.1145/3406325.3451065.
[14] Shuichi Hirahara. Symmetry of information from meta-complexity. In Computational Complexity Conference (CCC), pages 26:1–26:41, 2022. doi:10.4230/LIPIcs.CCC.2022.26.
[15] Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira. A duality between one-way functions and average-case symmetry of information. In Symposium on Theory of Computing (STOC), pages 1039–1050, 2023. doi:10.1145/3564246.3585138.
[16] Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Exact search-to-decision reductions for time-bounded Kolmogorov complexity. In Computational Complexity Conference (CCC), pages 29:1–29:56, 2024. doi:10.4230/LIPIcs.CCC.2024.29.
[17] Shuichi Hirahara, Zhenjian Lu, and Mikito Nanashima. Optimal coding for randomized kolmogorov complexity and its applications. In Symposium on Foundations of Computer Science (FOCS), pages 369–378, 2024. doi:10.1109/FOCS61266.2024.00030.
[18] Shuichi Hirahara, Zhenjian Lu, and Igor C. Oliveira. One-way functions and pKt complexity. In Theory of Cryptography (TCC), pages 253–286, 2024. doi:10.1007/978-3-031-78011-0_9.
[19] Shuichi Hirahara and Mikito Nanashima. Learning in Pessiland via inductive inference. In Symposium on Foundations of Computer Science (FOCS), pages 447–457, 2023. doi:10.1109/FOCS57990.2023.00033.
[20] Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira. Equivalence between coding and complexity lower bounds. Electron. Colloquium Comput. Complex., TR25, 2025. URL: https://eccc.weizmann.ac.il/report/2025/211.
[21] Rahul Ilango, Hanlin Ren, and Rahul Santhanam. Robustness of average-case meta-complexity via pseudorandomness. In Symposium on Theory of Computing (STOC), pages 1575–1583, 2022. doi:10.1145/3519935.3520051.
[22] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci., 65(4):672–694, 2002. doi:10.1016/S0022-0000(02)00024-7.
[23] Russell Impagliazzo and Avi Wigderson. Randomness vs time: Derandomization under a uniform assumption. J. Comput. Syst. Sci., 63(4):672–688, 2001. doi:10.1006/jcss.2001.1780.
[24] Valentine Kabanets. Easiness assumptions and hardness tests: Trading time for zero error. In Conference on Computational Complexity (CCC), pages 150–157, 2000. doi:10.1109/CCC.2000.856746.
[25] Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Symposium on Theory of Computing (STOC), pages 302–309, 1980. doi:10.1145/800141.804678.
[26] Troy Lee. Kolmogorov complexity and formula lower bounds. PhD thesis, University of Amsterdam, 2006.
[27] Leonid A. Levin. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii, 10(3):30–35, 1974.
[28] Leonid A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61(1):15–37, 1984. doi:10.1016/S0019-9958(84)80060-1.
[29] Jiatu Li, Edward Pyne, and Roei Tell. Distinguishing, predicting, and certifying: On the long reach of partial notions of pseudorandomness. In Symposium on Foundations of Computer Science (FOCS), pages 1–13, 2024. doi:10.1109/FOCS61266.2024.00095.
[30] Yanyi Liu and Rafael Pass. On one-way functions and Kolmogorov complexity. In Symposium on Foundations of Computer Science (FOCS), pages 1243–1254, 2020. doi:10.1109/FOCS46700.2020.00118.
[31] Yanyi Liu and Rafael Pass. One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions. In Annual Cryptology Conference (CRYPTO), pages 645–673, 2023. doi:10.1007/978-3-031-38545-2_21.
[32] Yanyi Liu and Rafael Pass. On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth. In Theory of Cryptography (TCC), pages 222–252, 2024. doi:10.1007/978-3-031-78011-0_8.
[33] Yanyi Liu and Rafael Pass. Hardness along the boundary towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity. In Annual Cryptology Conference (CRYPTO), 2025. doi:10.1007/978-3-032-01855-7_20.
[34] Zhenjian Lu, Noam Mazor, Igor C. Oliveira, and Rafael Pass. Lower bounds on the overhead of indistinguishability obfuscation. IACR Cryptol. ePrint Arch., page 1524, 2024. URL: https://eprint.iacr.org/2024/1524.
[35] Zhenjian Lu and Igor C. Oliveira. An efficient coding theorem via probabilistic representations and its applications. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 94:1–94:20, 2021. doi:10.4230/LIPIcs.ICALP.2021.94.
[36] Zhenjian Lu and Igor C. Oliveira. Theory and applications of probabilistic Kolmogorov complexity. Bull. EATCS, 137, 2022. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/700.
[37] Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam. On the complexity of avoiding heavy elements. In Symposium on Foundations of Computer Science (FOCS), pages 2403–2412, 2024. doi:10.1109/FOCS61266.2024.00140.
[38] Zhenjian Lu, Igor C. Oliveira, and Marius Zimand. Optimal coding theorems in time-bounded Kolmogorov complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 92:1–92:14, 2022. doi:10.4230/LIPIcs.ICALP.2022.92.
[39] Zhenjian Lu and Rahul Santhanam. Impagliazzo’s worlds through the lens of conditional Kolmogorov complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 110:1–110:17, 2024. doi:10.4230/LIPIcs.ICALP.2024.110.
[40] Igor C. Oliveira. Randomness and intractability in Kolmogorov complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 32:1–32:14, 2019. doi:10.4230/LIPIcs.ICALP.2019.32.
[41] Igor C. Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1–18:49, 2017. doi:10.4230/LIPIcs.CCC.2017.18.
[42] Rahul Santhanam. An algorithmic approach to uniform lower bounds. In Computational Complexity Conference (CCC), pages 35:1–35:26, 2023. doi:10.4230/LIPIcs.CCC.2023.35.
[43] Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331–364, 2007. doi:10.1007/s00037-007-0233-x.

[bib.bib1] [1] Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467–1493, 2006. doi:10.1137/050628994.

[bib.bib2] [2] Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci., 77(1):14–40, 2011. doi:10.1016/j.jcss.2010.06.004.

[bib.bib3] [3] Luis Filipe Coelho Antunes and Lance Fortnow. Worst-case running times for average-case algorithms. In Conference on Computational Complexity (CCC), pages 298–303, 2009. doi:10.1109/CCC.2009.12.

[bib.bib4] [4] László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex., 1:3–40, 1991. doi:10.1007/BF01200056.

[bib.bib5] [5] László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307–318, 1993. doi:10.1007/BF01275486.

[bib.bib6] [6] Marshall Ball, Yanyi Liu, Noam Mazor, and Rafael Pass. Kolmogorov comes to cryptomania: On interactive Kolmogorov complexity and key-agreement. In Symposium on Foundations of Computer Science (FOCS), pages 458–483, 2023. doi:10.1109/FOCS57990.2023.00034.

[bib.bib7] [7] Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional lower bounds against advice. In International Colloquium on Automata, Languages and Programming (ICALP), pages 195–209, 2009. doi:10.1007/978-3-642-02927-1_18.

[bib.bib8] [8] Harry Buhrman and Steven Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 116–127, 1992. doi:10.1007/3-540-56287-7_99.

[bib.bib9] [9] Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Conference on Computational Complexity (CCC), pages 10:1–10:24, 2016. doi:10.4230/LIPIcs.CCC.2016.10.

[bib.bib10] [10] Halley Goldberg and Valentine Kabanets. Improved learning from Kolmogorov complexity. In Computational Complexity Conference (CCC), pages 12:1–12:29, 2023. doi:10.4230/LIPIcs.CCC.2023.12.

[bib.bib11] [11] Halley Goldberg and Valentine Kabanets. Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM), pages 51:1–51:19, 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.51.

[bib.bib12] [12] Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov complexity with applications to average-case complexity. In Computational Complexity Conference (CCC), pages 16:1–16:60, 2022. doi:10.4230/LIPIcs.CCC.2022.16.

[bib.bib13] [13] Shuichi Hirahara. Average-case hardness of NP from exponential worst-case hardness assumptions. In Symposium on Theory of Computing (STOC), pages 292–302, 2021. doi:10.1145/3406325.3451065.

[bib.bib14] [14] Shuichi Hirahara. Symmetry of information from meta-complexity. In Computational Complexity Conference (CCC), pages 26:1–26:41, 2022. doi:10.4230/LIPIcs.CCC.2022.26.

[bib.bib15] [15] Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira. A duality between one-way functions and average-case symmetry of information. In Symposium on Theory of Computing (STOC), pages 1039–1050, 2023. doi:10.1145/3564246.3585138.

[bib.bib16] [16] Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Exact search-to-decision reductions for time-bounded Kolmogorov complexity. In Computational Complexity Conference (CCC), pages 29:1–29:56, 2024. doi:10.4230/LIPIcs.CCC.2024.29.

[bib.bib17] [17] Shuichi Hirahara, Zhenjian Lu, and Mikito Nanashima. Optimal coding for randomized kolmogorov complexity and its applications. In Symposium on Foundations of Computer Science (FOCS), pages 369–378, 2024. doi:10.1109/FOCS61266.2024.00030.

[bib.bib18] [18] Shuichi Hirahara, Zhenjian Lu, and Igor C. Oliveira. One-way functions and pKt complexity. In Theory of Cryptography (TCC), pages 253–286, 2024. doi:10.1007/978-3-031-78011-0_9.

[bib.bib19] [19] Shuichi Hirahara and Mikito Nanashima. Learning in Pessiland via inductive inference. In Symposium on Foundations of Computer Science (FOCS), pages 447–457, 2023. doi:10.1109/FOCS57990.2023.00033.

[bib.bib20] [20] Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira. Equivalence between coding and complexity lower bounds. Electron. Colloquium Comput. Complex., TR25, 2025. URL: https://eccc.weizmann.ac.il/report/2025/211.

[bib.bib21] [21] Rahul Ilango, Hanlin Ren, and Rahul Santhanam. Robustness of average-case meta-complexity via pseudorandomness. In Symposium on Theory of Computing (STOC), pages 1575–1583, 2022. doi:10.1145/3519935.3520051.

[bib.bib22] [22] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci., 65(4):672–694, 2002. doi:10.1016/S0022-0000(02)00024-7.

[bib.bib23] [23] Russell Impagliazzo and Avi Wigderson. Randomness vs time: Derandomization under a uniform assumption. J. Comput. Syst. Sci., 63(4):672–688, 2001. doi:10.1006/jcss.2001.1780.

[bib.bib24] [24] Valentine Kabanets. Easiness assumptions and hardness tests: Trading time for zero error. In Conference on Computational Complexity (CCC), pages 150–157, 2000. doi:10.1109/CCC.2000.856746.

[bib.bib25] [25] Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Symposium on Theory of Computing (STOC), pages 302–309, 1980. doi:10.1145/800141.804678.

[bib.bib26] [26] Troy Lee. Kolmogorov complexity and formula lower bounds. PhD thesis, University of Amsterdam, 2006.

[bib.bib27] [27] Leonid A. Levin. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii, 10(3):30–35, 1974.

[bib.bib28] [28] Leonid A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61(1):15–37, 1984. doi:10.1016/S0019-9958(84)80060-1.

[bib.bib29] [29] Jiatu Li, Edward Pyne, and Roei Tell. Distinguishing, predicting, and certifying: On the long reach of partial notions of pseudorandomness. In Symposium on Foundations of Computer Science (FOCS), pages 1–13, 2024. doi:10.1109/FOCS61266.2024.00095.

[bib.bib30] [30] Yanyi Liu and Rafael Pass. On one-way functions and Kolmogorov complexity. In Symposium on Foundations of Computer Science (FOCS), pages 1243–1254, 2020. doi:10.1109/FOCS46700.2020.00118.

[bib.bib31] [31] Yanyi Liu and Rafael Pass. One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions. In Annual Cryptology Conference (CRYPTO), pages 645–673, 2023. doi:10.1007/978-3-031-38545-2_21.

[bib.bib32] [32] Yanyi Liu and Rafael Pass. On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth. In Theory of Cryptography (TCC), pages 222–252, 2024. doi:10.1007/978-3-031-78011-0_8.

[bib.bib33] [33] Yanyi Liu and Rafael Pass. Hardness along the boundary towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity. In Annual Cryptology Conference (CRYPTO), 2025. doi:10.1007/978-3-032-01855-7_20.

[bib.bib34] [34] Zhenjian Lu, Noam Mazor, Igor C. Oliveira, and Rafael Pass. Lower bounds on the overhead of indistinguishability obfuscation. IACR Cryptol. ePrint Arch., page 1524, 2024. URL: https://eprint.iacr.org/2024/1524.

[bib.bib35] [35] Zhenjian Lu and Igor C. Oliveira. An efficient coding theorem via probabilistic representations and its applications. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 94:1–94:20, 2021. doi:10.4230/LIPIcs.ICALP.2021.94.

[bib.bib36] [36] Zhenjian Lu and Igor C. Oliveira. Theory and applications of probabilistic Kolmogorov complexity. Bull. EATCS, 137, 2022. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/700.

[bib.bib37] [37] Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam. On the complexity of avoiding heavy elements. In Symposium on Foundations of Computer Science (FOCS), pages 2403–2412, 2024. doi:10.1109/FOCS61266.2024.00140.

[bib.bib38] [38] Zhenjian Lu, Igor C. Oliveira, and Marius Zimand. Optimal coding theorems in time-bounded Kolmogorov complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 92:1–92:14, 2022. doi:10.4230/LIPIcs.ICALP.2022.92.

[bib.bib39] [39] Zhenjian Lu and Rahul Santhanam. Impagliazzo’s worlds through the lens of conditional Kolmogorov complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 110:1–110:17, 2024. doi:10.4230/LIPIcs.ICALP.2024.110.

[bib.bib40] [40] Igor C. Oliveira. Randomness and intractability in Kolmogorov complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 32:1–32:14, 2019. doi:10.4230/LIPIcs.ICALP.2019.32.

[bib.bib41] [41] Igor C. Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1–18:49, 2017. doi:10.4230/LIPIcs.CCC.2017.18.

[bib.bib42] [42] Rahul Santhanam. An algorithmic approach to uniform lower bounds. In Computational Complexity Conference (CCC), pages 35:1–35:26, 2023. doi:10.4230/LIPIcs.CCC.2023.35.

[bib.bib43] [43] Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331–364, 2007. doi:10.1007/s00037-007-0233-x.

Equivalence Between Coding and Complexity Lower Bounds

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Context and Motivation

1.2 Results

Summary.

Organization.

1.2.1 Coding for Deterministic Time-Bounded Kolmogorov Complexity

Theorem 1.

Corollary 2.

1.2.2 Coding for Non-Deterministic Time-Bounded Kolmogorov Complexity

Theorem 3.

1.2.3 Coding for Zero-Error Time-Bounded Kolmogorov Complexity

Theorem 4.

1.2.4 Complexity Separations and Meta-Complexity

Theorem 5.

Theorem 6.

Theorem 7.

1.3 Summary of Equivalences and Concluding Remarks

1.4 Techniques

Equivalence Between Coding for 𝗞𝘁 and 𝗘𝗫𝗣≠𝗕𝗣𝗣.

Equivalence Between Coding for 𝗻𝗞𝘁 and 𝗡𝗘𝗫𝗣≠𝗕𝗣𝗣.

Equivalence Between Coding for 𝘇𝗞𝘁 and 𝗽𝗿𝗭𝗣𝗘𝗫𝗣≠𝗽𝗿𝗕𝗣𝗣.

Complexity Separations and Meta-Complexity.

Remainder of the paper.

2 Preliminaries

2.1 Time-Bounded Kolmogorov Complexity

Definition 8 (𝖪𝗍 [28]).

Definition 9 (𝗋𝖪𝗍 [40]).

Definition 10 (𝗓𝖪𝗍).

Definition 11 (𝗇𝖪𝗍).

2.2 Pseudorandomness

Theorem 12 ([5]).

Theorem 13 ([23, 43]).

2.3 Complexity Theory and Diagonalization Against Advice

Lemma 14.

Proof.

Corollary 15.

Corollary 16.

3 Coding for Deterministic Time-Bounded Kolmogorov Complexity

3.1 Equivalence Between Coding for 𝗞𝘁 and 𝗘𝗫𝗣≠𝗕𝗣𝗣

Theorem 1. [Restated, see original statement.]

Proof.

3.1.1 𝗘𝗫𝗣≠𝗕𝗣𝗣 from Non-Trivial Coding for 𝗞𝘁

Lemma 17.

Proof.

Claim 18.

Proof of Claim 18.

3.1.2 Weak Coding for 𝗞𝘁 from 𝗘𝗫𝗣≠𝗕𝗣𝗣

Lemma 19.

Lemma 20.

Proof.

Case 1: 𝗣𝗦𝗣𝗔𝗖𝗘⊈𝗕𝗣𝗣.

Case 2: 𝗣𝗦𝗣𝗔𝗖𝗘⊆𝗕𝗣𝗣.

Proof of Lemma 19.

3.2 Stronger Lower Bounds from Near-Optimal Coding for 𝗞𝘁

Theorem 21.

Proof.

4 Coding for Non-Deterministic Time-Bounded Kolmogorov Complexity

4.1 Equivalence Between Coding for 𝗻𝗞𝘁 and 𝗡𝗘𝗫𝗣≠𝗕𝗣𝗣

Theorem 22.

Proof.

4.1.1 𝗡𝗘𝗫𝗣≠𝗕𝗣𝗣 from Non-Trivial Coding for 𝗻𝗞𝘁

Lemma 23.

Proof.

Claim 24.

Proof Sketch of Claim 24.

Claim 25.

Proof of Claim 25.

Equivalence Between Coding for $\mathsf{Kt}$ and $\mathsf{EXP}\neq\mathsf{BPP}$ .

Equivalence Between Coding for $\mathsf{nKt}$ and $\mathsf{NEXP}\neq\mathsf{BPP}$ .

Equivalence Between Coding for $\mathsf{zKt}$ and $\mathsf{prZPEXP}\neq\mathsf{prBPP}$ .

Definition 8 ( $\mathsf{Kt}$ [28]).

Definition 9 ( $\mathsf{rKt}$ [40]).

Definition 10 ( $\mathsf{zKt}$ ).

Definition 11 ( $\mathsf{nKt}$ ).

3.1 Equivalence Between Coding for $\mathsf{Kt}$ and $\mathsf{EXP}\neq\mathsf{BPP}$

3.1.1 $\mathsf{EXP}\neq\mathsf{BPP}$ from Non-Trivial Coding for $\mathsf{Kt}$

3.1.2 Weak Coding for $\mathsf{Kt}$ from $\mathsf{EXP}\neq\mathsf{BPP}$

Case 1: $\mathsf{PSPACE}\not\subseteq\mathsf{BPP}$ .

Case 2: $\mathsf{PSPACE}\subseteq\mathsf{BPP}$ .

3.2 Stronger Lower Bounds from Near-Optimal Coding for $\mathsf{Kt}$

4.1 Equivalence Between Coding for $\mathsf{nKt}$ and $\mathsf{NEXP}\neq\mathsf{BPP}$

4.1.1 $\mathsf{NEXP}\neq\mathsf{BPP}$ from Non-Trivial Coding for $\mathsf{nKt}$

4.1.2 Weak Coding for $\mathsf{nKt}$ from $\mathsf{NEXP}\neq\mathsf{BPP}$

Case 1: $\mathsf{PSPACE}\not\subseteq\mathsf{BPP}$ .

Case 2: $\mathsf{PSPACE}\subseteq\mathsf{BPP}$ .

4.2 Equivalence Between Coding for $\mathsf{Kt}^{\mathsf{NP}}$ and $\mathsf{EXP}^{\mathsf{NP}}\neq\mathsf{BPP}$