Worst-case to average-case reductions for time-bounded Kolmogorov complexity against heuristics that may err

Time-bounded Kolmogorov complexity $K^t(x)$ — the length of the shortest program printing $x$ within time $t(|x|)$ — sits at the center of meta-complexity, the study of computational problems whose input encodes another object's complexity. Hirahara (FOCS 2018) constructed a non-black-box worst-case to average-case reduction for approximating $K^t$: if the average-case version of the gap problem admits an errorless heuristic (one that outputs either the correct answer or a special failure symbol $\perp$), then $K^t$ can be approximated in the worst case. Liu and Pass (FOCS 2020) then proved unconditionally that one-way functions exist if and only if $K^{\mathrm{poly}}$ is mildly hard on average against ordinary heuristics that may err — a strictly stronger hardness notion their proof obtains directly, without any worst-case to average-case reduction. The open problem, stated in Hirahara (FOCS 2018, Open Problems) and quoted by Liu–Pass (Section 1.1), is to extend the non-black-box worst-case to average-case reduction for $K^{\mathrm{poly}}$ to heuristics that may err (two-sided error). Such a reduction is the missing link for converting worst-case hardness of time-bounded Kolmogorov complexity into average-case hardness of the form that yields one-way functions. As of 2026 the problem remains open: known partial progress includes a relativization barrier against relativizing proofs, an equivalence between closing the gap and building instance checkers for $K^{\mathrm{poly}}$, a conditional closure under an unproven padding conjecture, and unconditional workarounds for conditioned, boundary, or probabilistic variants of the problem.

Background

A one-way function (OWF) is a function that is easy to compute but hard to invert on average for any probabilistic polynomial-time (PPT) algorithm; the existence of OWFs is the minimal assumption underlying private-key cryptography (pseudorandom generators, encryption, digital signatures), and whether OWFs exist is arguably the central open problem of cryptography.

Kolmogorov complexity $K(x)$ measures the amount of randomness in an individual string $x$: the length of the shortest program, for a fixed universal Turing machine $U$, that outputs $x$. Its time-bounded variant $K^t(x)$ additionally requires the program to halt within $t(|x|)$ steps. Computing or approximating $K^t$ is a canonical meta-complexity problem (a problem about the complexity of its own input), studied since Trakhtenbrot's early survey in the Soviet literature; MINKT denotes the problem of computing $K^t(x)$ exactly, and Gap-MINKT its promise version, which distinguishes strings with $K^t(x)\le s$ from strings with $K^{t'}(x)>s'$ for polynomially related time bounds and an explicit gap.

Average-case complexity studies distributional problems $(L,D)$, where $D$ is a distribution over inputs, and comes in two standard heuristic models. An errorless heuristic for $(L,D)$ must output, on every input, either the correct answer $L(x)$ or a special symbol $\perp$ indicating failure, and it may output $\perp$ only on a small fraction of the $D$-mass; the class of problems solvable by randomized polynomial-time errorless heuristics is denoted AvgBPP. An ordinary (error-prone, or erring) heuristic may simply output a wrong answer on a small fraction of the $D$-mass; the corresponding class is HeurBPP. Hardness against erring heuristics is strictly stronger than hardness against errorless ones: for example, a random 3SAT formula with many clauses is unsatisfiable with high probability, so outputting "unsatisfiable" is a trivially correct erring heuristic, while an errorless heuristic for the same task is not known (and its nonexistence is related to Feige's Random 3SAT conjecture).

A worst-case to average-case reduction is an efficient (typically randomized) reduction proving that if the average-case version of a problem is easy, then some worst-case problem is easy — contrapositively, worst-case hardness implies average-case hardness. Black-box such reductions are known to be impossible for most of NP, and Hirahara (FOCS 2018) overcame this barrier with the first non-black-box reduction within NP (a reduction that may use the code of the average-case algorithm rather than merely querying it as an oracle): if the average-case version of Gap-MINKT (over the uniform distribution) admits an errorless polynomial-time heuristic, then MINKT can be approximated within an additive $\tilde{O}(\sqrt{k})$ error (where $k$ is the complexity value) by a zero-error randomized polynomial-time algorithm in the worst case. His proof exploits that the Yes instances of the underlying problem are sparse — an argument that breaks when the heuristic may err without announcing its failures.

Liu and Pass (FOCS 2020) proved, unconditionally and by a direct construction, that OWFs exist if and only if $K^{\mathrm{poly}}$ is mildly hard on average against ordinary erring PPT algorithms over the uniform distribution (for every polynomial time bound $t(n)\ge(1+\varepsilon)n$). Their proof, however, does not proceed through a worst-case to average-case reduction: worst-case hardness of computing $K^{\mathrm{poly}}$ does not by itself yield the erring average-case hardness that their equivalence needs. The two landmark results therefore sit on opposite sides of a gap that Hirahara himself singled out: his reduction covers only errorless heuristics, while the OWF-relevant hardness notion is the erring one. Closing this gap is also a central step in the program, structured by Impagliazzo's five possible worlds, of ruling out Heuristica (a world where NP is worst-case hard but easy on average in the errorless sense) and Pessiland (a world where NP is hard on average yet no OWF exists), since a worst-case to average-case reduction for erring heuristics would convert worst-case hardness of time-bounded Kolmogorov complexity — and, via known NP-hardness of approximating $K^t$ under randomized reductions, potentially the worst-case hardness of NP — into the existence of one-way functions.

Hirahara and Santhanam (ITCS 2022) showed that closing the errorless/erring gap for NP is equivalent to constructing efficient non-uniform average-case non-adaptive instance checkers for NP — a program $M$ with oracle access to a candidate solver that verifies the solver's answer on each individual instance with high probability — themselves a long-standing open target; Hirahara and Nanashima (CCC 2022) constructed an oracle (an auxiliary black-box subroutine made available to every machine, used to delimit the power of relativizing proofs) relative to which NP is easy on average for erring heuristics yet hard for errorless ones, so any solution must use non-relativizing techniques.

Problem Statement

Construct a worst-case to average-case reduction for time-bounded Kolmogorov complexity that is sound against ordinary heuristics allowed to err (two-sided error), extending Hirahara's non-black-box reduction for errorless heuristics.

Concretely: fix a universal Turing machine $U$ and let $K^t(x)$ denote the $t$-time-bounded Kolmogorov complexity of $x$; let Gap-MINKT denote the promise problem of distinguishing $K^t(x)\le s$ from $K^{t'}(x)>s'$ for polynomially related time bounds with an explicit gap, where $s$ and $s'$ are fixed so that each of the Yes side and the No side carries uniform mass greater than $1/3$ (so that no constant-answer heuristic satisfies the error bound stated next). The requested theorem has the following shape: if Gap-MINKT admits a randomized polynomial-time heuristic over the uniform distribution that errs with probability at most $1/3$ (i.e., Gap-MINKT is in HeurBPP), then the corresponding worst-case problem becomes easy — specifically, approximating MINKT within the quality achieved in the errorless case (additive $\tilde{O}(\sqrt{k})$) is in BPP. Contrapositively, worst-case hardness of approximating $K^{\mathrm{poly}}$ implies average-case hardness of $K^{\mathrm{poly}}$ against heuristics that may err — the precise form that combines with the Liu–Pass characterization to derive one-way functions from worst-case hardness assumptions.

The reduction may be randomized and non-black-box, and may trade reduction efficiency against approximation quality, mirroring the flexibility of the errorless theorem of Hirahara (FOCS 2018) that it extends. Answers that hold only for errorless heuristics, or only for modified problems (conditioned, distributional, boundary, or probabilistic variants), do not resolve the stated problem, though they constitute relevant progress.

References

1. Yanyi Liu and Rafael Pass, "On One-way Functions and Kolmogorov Complexity", FOCS 2020. arXiv:2009.11514, DOI: 10.48550/arXiv.2009.11514, https://arxiv.org/abs/2009.11514
2. Shuichi Hirahara, "Non-black-box Worst-case to Average-case Reductions within NP", FOCS 2018. DOI: 10.1109/FOCS.2018.00032, ECCC TR18-138, https://eccc.weizmann.ac.il/report/2018/138/ (journal version: SIAM Journal on Computing, 2023, DOI: 10.1137/19m124705x)
3. Shuichi Hirahara and Rahul Santhanam, "Errorless Versus Error-Prone Average-Case Complexity", ITCS 2022. DOI: 10.4230/LIPIcs.ITCS.2022.84, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.84
4. Shuichi Hirahara and Mikito Nanashima, "Finding Errorless Pessiland in Error-Prone Heuristica", CCC 2022. DOI: 10.4230/LIPIcs.CCC.2022.25, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.25
5. Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira, "Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity", CCC 2022. DOI: 10.4230/LIPIcs.CCC.2022.16, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.16
6. Michael Saks and Rahul Santhanam, "On Randomized Reductions to the Random Strings", CCC 2022. DOI: 10.4230/LIPIcs.CCC.2022.29, https://eccc.weizmann.ac.il/report/2022/074/
7. Shuichi Hirahara, "Capturing One-Way Functions via NP-Hardness of Meta-Complexity", STOC 2023. DOI: 10.1145/3564246.3585130, ECCC TR23-037, https://eccc.weizmann.ac.il/report/2023/037/
8. Yanyi Liu and Rafael Pass, "On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity", ECCC TR23-103, 2023, https://eccc.weizmann.ac.il/report/2023/103/ (journal version: "On One-Way Functions, the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity, and Computational Depth", TCC 2024, DOI: 10.1007/978-3-031-78011-0_8, https://doi.org/10.1007/978-3-031-78011-0_8)
9. Yanyi Liu and Rafael Pass, "Hardness Along the Boundary: Towards One-Way Functions from the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity", CRYPTO 2025. DOI: 10.1007/978-3-032-01855-7_20, ECCC TR25-125, https://eccc.weizmann.ac.il/report/2025/125/
10. Yanyi Liu, Noam Mazor, and Rafael Pass, "Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity", 2026. ECCC TR26-051, https://eccc.weizmann.ac.il/report/2026/051/
11. Shuichi Hirahara and Mikito Nanashima, "A Sharp Characterization of Pessiland", STOC 2026. DOI: 10.1145/3798129.3800755, https://doi.org/10.1145/3798129.3800755