Errorless versus two-sided-error average-case hardness of MKtP: the Liu–Pass gap between EXP ≠ BPP and one-way functions

Liu and Pass (CRYPTO 2021; CACM 2023) proved that the minimum Levin–Kolmogorov complexity problem MKtP is mildly hard on average against errorless heuristics if and only if EXP ≠ BPP, and mildly hard on average against two-sided-error heuristics if and only if infinitely-often one-way functions exist. The central open question they identified is whether the first statement implies the second: does MKtP ∉ Avg_neg BPP imply MKtP ∉ Heur_neg BPP? By their Theorem 5.1 this is exactly the question whether the weak uniform assumption EXP ≠ BPP implies the existence of infinitely-often one-way functions, and by their Theorem 5.2 an affirmative answer would prove NP ≠ P. As of August 2026 the question remains open.

Background

Foundations. A one-way function (OWF) is a polynomial-time computable function that no probabilistic polynomial-time (PPT) algorithm can invert on more than a negligible (smaller than any inverse polynomial) fraction of inputs. OWFs are the minimal assumption of private-key cryptography: they are equivalent to pseudorandom generators, private-key encryption, and commitments. A relaxed variant, the infinitely-often OWF (ioOWF), need only be hard to invert at infinitely many input lengths; its existence still implies $\mathrm{NP} \ne \mathrm{P}$, since inverting a given function is an NP search problem. Whether OWFs can be derived from any worst-case hardness assumption is a foundational open problem. Impagliazzo's five-worlds taxonomy frames the landscape: in Heuristica, NP problems are easy on average; in Pessiland, NP is hard on average yet no OWFs exist — a world with neither algorithms nor cryptography. The question studied here is a sharp meta-complexity incarnation of the Heuristica–Pessiland boundary.

Levin–Kolmogorov complexity. Meta-complexity studies computational problems whose task is to compute a complexity measure. The Levin–Kolmogorov complexity of a string is $Kt(x) = \min_{\Pi, t}\{\lvert\Pi\rvert + \lceil \log t \rceil : U(\Pi, 1^t) = x\}$, where $U$ is a fixed universal Turing machine and $U(\Pi, 1^t)$ is the output of program $\Pi$ after $t$ steps; running time is charged only logarithmically, so polynomial-time computation counts as "cheap". One always has $Kt(x) \le \lvert x\rvert + O(1)$. The decision problem $\mathrm{MKtP}$ consists of all pairs $(x, k)$, with $k \in \{0,1\}^{\lceil \log \lvert x\rvert \rceil}$, such that $Kt(x) \le k$. Allender, Buhrman, Koucký, van Melkebeek, and Ronneburger proved that $\mathrm{MKtP}$ is EXP-complete under P/poly reductions (P/poly is the class of languages decidable by polynomial-size circuit families), so hardness of MKtP is a stand-in for the hardness of EXP — deterministic exponential time — itself.

Two average-case error models. Average-case complexity distinguishes errorless from two-sided-error tractability. Following Definitions 2.4 and 2.5 of the source, with respect to the uniform distribution over $n$-bit inputs: $L \in \mathrm{Heur}_{\mathrm{neg}}\mathrm{BPP}$ if for every polynomial $p$ there exists a PPT heuristic $H$ such that for all sufficiently large $n$, $\Pr_{x \leftarrow \{0,1\}^n}[H(x) = L(x)] \ge 1 - 1/p(n)$ (the heuristic may err, but rarely); and $L \in \mathrm{Avg}_{\mathrm{neg}}\mathrm{BPP}$ if for every polynomial $p$ there exists a PPT heuristic $H$ such that for all sufficiently large $n$ and every $x \in \{0,1\}^n$, $\Pr[H(x) \in \{L(x), \bot\}] \ge 0.9$ and $\Pr_{x \leftarrow \{0,1\}^n}[H(x) = \bot] \le 1/p(n)$ — an errorless heuristic outputs a wrong (non-$\bot$) answer with probability at most $0.1$ on each instance, a slack that standard confidence amplification reduces to negligible, and abstains by outputting $\bot$ ("I don't know") on only a negligible fraction of typical inputs. Here BPP is bounded-error probabilistic polynomial time, and non-membership in either class is an infinitely-often, mild (inverse-polynomial-scale) average-case hardness statement. Every errorless heuristic can be converted into a two-sided-error heuristic by guessing randomly whenever it abstains (after standard confidence amplification), so $\mathrm{Avg}_{\mathrm{neg}}\mathrm{BPP} \subseteq \mathrm{Heur}_{\mathrm{neg}}\mathrm{BPP}$: two-sided-error hardness always implies errorless hardness. The open question is the converse.

The characterization theorems. Liu and Pass (FOCS 2020) proved that OWFs exist if and only if the parametrized time-bounded Kolmogorov complexity problem $K^t$ is mildly hard on average against two-sided-error algorithms. Liu and Pass (CRYPTO 2021; the CACM 2023 article is its Research Highlights version) extended the characterization to Levin's non-parametrized complexity: (i) $\mathrm{MKtP} \notin \mathrm{Heur}_{\mathrm{neg}}\mathrm{BPP}$ if and only if ioOWFs exist; and (ii) $\mathrm{MKtP} \notin \mathrm{Avg}_{\mathrm{neg}}\mathrm{BPP}$ if and only if $\mathrm{EXP} \ne \mathrm{BPP}$. Note that $\mathrm{EXP} \ne \mathrm{BPP}$ is itself unproved — it is exactly the weak uniform assumption this research program tries to base cryptography on. The proof of (i) rests on the fact that all but an $\varepsilon$ fraction of $n$-bit strings admit a Kt-witness (a program attaining the minimum) that runs in time $O(1/\varepsilon)$, which allows the FOCS 2020 OWF construction to be carried over to $Kt$. The proof of (ii) goes through uniform derandomization: by an Impagliazzo–Wigderson-style argument, $\mathrm{EXP} \ne \mathrm{BPP}$ yields an inefficient infinitely-often pseudorandom generator — a PRG is a deterministic map stretching short seeds into longer strings that no PPT algorithm distinguishes from uniform, and "inefficient" PRGs may take exponential time — of the form $G : \{0,1\}^{n^\varepsilon} \to \{0,1\}^n$ computable in time $2^{O(n^\gamma)}$; every output of $G$ has $Kt$-complexity at most $n - 1$, whereas a uniformly random string has $Kt$-complexity greater than $n - 1$ with probability at least $1/2$, and pseudorandomness contradicts the existence of an errorless heuristic for MKtP, which would have to classify these two kinds of strings correctly or abstain only negligibly often.

The gap. Combining (i) and (ii), the only remaining step toward ioOWFs from the assumption $\mathrm{EXP} \ne \mathrm{BPP}$ is the seemingly minor technical gap between two-sided-error and errorless average-case hardness of MKtP. In contrapositive form, the gap asks whether every two-sided-error heuristic for MKtP — an algorithm that is usually right but may err without knowing it — can be converted into an errorless one that errs with probability at most $0.1$ on each instance (amplifiable to negligible). Closing this gap would base (infinitely-often) cryptography on the hardness of EXP; by Theorem 5.2 of the source, any such closure also proves $\mathrm{NP} \ne \mathrm{P}$.

Problem Statement

Fix a universal Turing machine $U$ and define the Levin–Kolmogorov complexity of a string $x$ by

$$Kt(x) = \min_{\Pi \in \{0,1\}^*,\, t \in \mathbb{N}} \{\lvert\Pi\rvert + \lceil \log t \rceil : U(\Pi, 1^t) = x\},$$

where $U(\Pi, 1^t)$ is the output of program $\Pi$ after $t$ steps, and let

$$\mathrm{MKtP} = \{(x, k) : k \in \{0,1\}^{\lceil \log \lvert x\rvert \rceil},\ Kt(x) \le k\}.$$

Following Definitions 2.4 and 2.5 of Liu and Pass (CRYPTO 2021), with respect to the uniform distribution over inputs: $L \in \mathrm{Heur}_{\mathrm{neg}}\mathrm{BPP}$ if for every polynomial $p$ there exists a probabilistic polynomial-time heuristic $H$ such that for all sufficiently large $n$,

$$\Pr_{x \leftarrow \{0,1\}^n}[H(x) = L(x)] \ge 1 - \frac{1}{p(n)},$$

and $L \in \mathrm{Avg}_{\mathrm{neg}}\mathrm{BPP}$ if for every polynomial $p$ there exists a probabilistic polynomial-time heuristic $H$ such that for all sufficiently large $n$ and every $x \in \{0,1\}^n$,

$$\Pr[H(x) \in \{L(x), \bot\}] \ge 0.9 \quad\text{and}\quad \Pr_{x \leftarrow \{0,1\}^n}[H(x) = \bot] \le \frac{1}{p(n)}.$$

When these definitions are applied to $\mathrm{MKtP}$, an instance is a pair $(x,k)$ and the uniform distribution over instances means $x \leftarrow \{0,1\}^n$ and $k \leftarrow \{0,1\}^{\lceil \log n \rceil}$ chosen independently and uniformly, as in the source's proofs for MKtP.

Does

$$\mathrm{MKtP} \notin \mathrm{Avg}_{\mathrm{neg}}\mathrm{BPP} \implies \mathrm{MKtP} \notin \mathrm{Heur}_{\mathrm{neg}}\mathrm{BPP}?$$

Equivalently, by Theorem 5.1 of the source: does $\mathrm{EXP} \ne \mathrm{BPP}$ imply the existence of infinitely-often one-way functions? Here $\mathrm{EXP}$ denotes deterministic exponential time, $\mathrm{BPP}$ bounded-error probabilistic polynomial time, and an infinitely-often one-way function (ioOWF) is a polynomial-time computable function that no probabilistic polynomial-time algorithm can invert on more than a negligible — smaller than any inverse polynomial — fraction of inputs at infinitely many input lengths. Equivalently again, in contrapositive form: can every two-sided-error heuristic for MKtP — an algorithm that is usually right but may err unknowingly — be converted into an errorless heuristic that errs with probability at most $0.1$ on each instance (amplifiable to negligible) and abstains (outputs $\bot$) only negligibly often? A complete answer is either a proof of the implication in the standard (unrelativized) model of computation, or a proof that the implication fails, which by the source's characterization theorems amounts to proving $\mathrm{EXP} \ne \mathrm{BPP}$ while infinitely-often one-way functions do not exist. Results relative to oracles, conditional on additional unproved conjectures, or for probabilistic variants of $Kt$ do not resolve the question. An affirmative answer implies $\mathrm{NP} \ne \mathrm{P}$ (Theorem 5.2 of the source).

References

1. Yanyi Liu and Rafael Pass, On the Possibility of Basing Cryptography on EXP ≠ BPP, CRYPTO 2021 (Advances in Cryptology – CRYPTO 2021, LNCS 12826), DOI 10.1007/978-3-030-84242-0_2, https://doi.org/10.1007/978-3-030-84242-0_2; full version: IACR Cryptology ePrint Archive, Paper 2021/535, https://eprint.iacr.org/2021/535
2. Yanyi Liu and Rafael Pass, Toward Basing Cryptography on the Hardness of EXP, Communications of the ACM 66(5):91–99, 2023, DOI 10.1145/3587167, https://doi.org/10.1145/3587167
3. Yanyi Liu and Rafael Pass, On One-way Functions and Kolmogorov Complexity, FOCS 2020, arXiv:2009.11514, https://arxiv.org/abs/2009.11514
4. Russell Impagliazzo, A Personal View of Average-Case Complexity, Proceedings of the Tenth Annual IEEE Conference on Structure in Complexity Theory, 1995, DOI 10.1109/SCT.1995.514853, https://doi.org/10.1109/SCT.1995.514853
5. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger, Power from Random Strings, SIAM Journal on Computing 35(6):1467–1493, 2006, DOI 10.1137/050628994, https://doi.org/10.1137/050628994
6. Russell Impagliazzo and Avi Wigderson, Randomness vs Time: Derandomization under a Uniform Assumption, Journal of Computer and System Sciences 63(2), 2001 (preliminary version FOCS 1998), DOI 10.1006/jcss.2001.1780, https://doi.org/10.1006/jcss.2001.1780
7. Shuichi Hirahara and Rahul Santhanam, Errorless Versus Error-Prone Average-Case Complexity, ITCS 2022, LIPIcs vol. 215, pp. 84:1–84:23, DOI 10.4230/LIPIcs.ITCS.2022.84, https://doi.org/10.4230/LIPIcs.ITCS.2022.84
8. Shuichi Hirahara and Mikito Nanashima, Finding Errorless Pessiland in Error-Prone Heuristica, CCC 2022, LIPIcs vol. 234, DOI 10.4230/LIPIcs.CCC.2022.25, https://doi.org/10.4230/LIPIcs.CCC.2022.25
9. Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich, One-Way Functions and a Conditional Variant of MKTP, FSTTCS 2021, LIPIcs vol. 213, DOI 10.4230/LIPIcs.FSTTCS.2021.7, https://doi.org/10.4230/LIPIcs.FSTTCS.2021.7
10. Shuichi Hirahara, Capturing One-Way Functions via NP-Hardness of Meta-Complexity, STOC 2023, DOI 10.1145/3564246.3585130, https://doi.org/10.1145/3564246.3585130
11. Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor Carboni Oliveira, A Duality Between One-Way Functions and Average-Case Symmetry of Information, STOC 2023, ECCC Technical Report TR23-035, https://eccc.weizmann.ac.il/report/2023/035
12. Shuichi Hirahara, Zhenjian Lu, and Igor C. Oliveira, One-Way Functions and pKt Complexity, TCC 2024, DOI 10.1007/978-3-031-78011-0_9, https://doi.org/10.1007/978-3-031-78011-0_9; full version: ECCC Technical Report TR24-136, https://eccc.weizmann.ac.il/report/2024/136
13. Yanyi Liu and Rafael Pass, On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity, 2023, IACR Cryptology ePrint Archive, Paper 2023/1086, https://eprint.iacr.org/2023/1086
14. Yanyi Liu and Rafael Pass, Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity, 2025, IACR Cryptology ePrint Archive, Paper 2025/1497, https://eprint.iacr.org/2025/1497 (also ECCC TR25-125, https://eccc.weizmann.ac.il/report/2025/125)
15. Yanyi Liu and Rafael Pass, One-way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity, 2025, ECCC Technical Report TR25-202, https://eccc.weizmann.ac.il/report/2025/202 (also IACR ePrint 2025/2184, https://eprint.iacr.org/2025/2184)
16. Yanyi Liu, Noam Mazor, and Rafael Pass, Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity, 2026, IACR Cryptology ePrint Archive, Paper 2026/668, https://eprint.iacr.org/2026/668
17. Shuichi Hirahara and Mikito Nanashima, A Sharp Characterization of Pessiland, 2026, ECCC Technical Report TR26-052, https://eccc.weizmann.ac.il/report/2026/052