Equivalence of Worst-Case and Average-Case Hardness for NP (Excluding Heuristica)

Equivalence of Worst-Case and Average-Case Hardness for NP (Excluding Heuristica)

Definitions and mathematical statement

A distributional problem is a pair $(L,D)$, where $L$ is a language and $D=(D_n)$ is an efficiently described input distribution ensemble. In Levin's average-time convention, a correct deterministic decider $A$ is average-polynomial if for some $\varepsilon>0$, \[ \mathbb E_{x\sim D_n} T_A(x)^\varepsilon\le\operatorname{poly}(n). \] Write $\mathsf{AvgP}$ for this class. Distributional NP uses $L\in\mathsf{NP}$ and a prescribed efficient distribution class. The target is $\mathsf{NP}\nsubseteq\mathsf{P/poly}\Rightarrow\mathsf{DistNP}\nsubseteq\mathsf{AvgP}$. The catalogue leaves polynomial-time computable versus samplable ensembles implicit; these are distinct definitions and must not be interchanged without the relevant reduction theorem. The added Bogdanov--Trevisan survey gives both conventions and distinguishes errorless algorithms from heuristics allowed to return incorrect answers.

Formulation and concept references: [S1], [E1].

Short English statement

Does strong worst-case hardness in NP necessarily create an efficiently distributed NP problem that is hard on average?

Sources

• S1 A. Bogdanov, L. Trevisan, SIAM J. Comput. 36$4$:1119-1159, 2006. https://doi.org/10.1137/050634629. Catalogue formulation source.
• S2 Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions. https://eccc.weizmann.ac.il/report/2025/072/download. Catalogue research/status reference; not a proof endorsement.
• S3 Hardness of Computing Nondeterministic Kolmogorov Complexity. https://eccc.weizmann.ac.il/report/2025/203/. Catalogue research/status reference; not a proof endorsement.
• E1 Andrej Bogdanov and Luca Trevisan, Average-Case Complexity, Foundations and Trends in Theoretical Computer Science 2 $2006$, 1--106. https://andrejb.net/pubs/average-now.pdf. Added primary source: Definitions of distributional problems and average-polynomial time. Consulted 24 September 2026.
• E2 Andrej Bogdanov and Luca Trevisan, On Worst-Case to Average-Case Reductions for NP Problems, SIAM Journal on Computing 36$4$ $2006$, 1119--1159, DOI 10.1137/S0097539705446974. See also the precise nonadaptive formulation in Theorem 7.5 of [E1]. https://doi.org/10.1137/S0097539705446974. Added research source: Corrected identifier for the paper intended by [S1]; nonadaptive reduction barrier. The original [S1] is preserved. Consulted 24 September 2026.
• E3 Rahul Ilango and Alex Lombardi, Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions, ECCC TR25-072 $2025$, abstract and stated cryptographic hypotheses. https://eccc.weizmann.ac.il/report/2025/072/. Added research source: The additional obfuscation and fine-grained assumptions are retained, not treated as consequences of the target premise. Consulted 24 September 2026.
• E4 Jinqiao Hu, Zhenjian Lu and Igor Oliveira, Hardness of Computing Nondeterministic Kolmogorov Complexity, ECCC TR25-203, revision 2, 5 July 2026, Section 1.2.3 and Appendix B, including Corollary 59. https://eccc.weizmann.ac.il/report/2025/203/revision/2/download. Added research source: Recent meta-complexity implications and the remaining gap-version obstacle; not identified with the deterministic average-time assertion. Consulted 24 September 2026.

Equivalence of Worst-Case and Average-Case Hardness for NP (Excluding Heuristica)

Definitions and mathematical statement

A distributional problem is a pair $(L,D)$, where $L$ is a language and $D=(D_n)$ is an efficiently described input distribution ensemble. In Levin's average-time convention, a correct deterministic decider $A$ is average-polynomial if for some $\varepsilon>0$, \[ \mathbb E_{x\sim D_n} T_A(x)^\varepsilon\le\operatorname{poly}(n). \] Write $\mathsf{AvgP}$ for this class. Distributional NP uses $L\in\mathsf{NP}$ and a prescribed efficient distribution class. The target is $\mathsf{NP}\nsubseteq\mathsf{P/poly}\Rightarrow\mathsf{DistNP}\nsubseteq\mathsf{AvgP}$. The catalogue leaves polynomial-time computable versus samplable ensembles implicit; these are distinct definitions and must not be interchanged without the relevant reduction theorem. The added Bogdanov--Trevisan survey gives both conventions and distinguishes errorless algorithms from heuristics allowed to return incorrect answers.

Formulation and concept references: [S1], [E1].

Short English statement

Does strong worst-case hardness in NP necessarily create an efficiently distributed NP problem that is hard on average?

Research attempt

Current frontier and editorial note.

The reference designated [S1] has the bibliographic location of Bogdanov and Trevisan's On Worst-Case to Average-Case Reductions for NP Problems, but its DOI is not that paper's DOI. The original item is retained; [E2] supplies the corrected identifier. The relevant barrier concerns nonadaptive, robust worst-case-to-average-case reductions, not every imaginable connection between the two notions. The survey's Theorem 7.5 gives the conclusion $L\in\mathsf{NP/poly}\cap\mathsf{coNP/poly}$ for the stipulated nonadaptive reduction from $L$ to a distributional NP problem with a polynomial-time samplable distribution. [E1], [E2]

The July 2026 revision of Hu--Lu--Oliveira relates efficient computation of nondeterministic time-bounded Kolmogorov complexity to $\mathsf{NP}\subseteq\mathsf{BPP}$. Its Section 1.2.3 and Appendix B explicitly retain a gap-version obstacle to excluding PH-Heuristica. That is a different, unfinished implication; it does not establish the present deterministic $\mathsf{AvgP}$ target. [E4] Ilango--Lombardi's 2025 cryptographic reductions use additional indistinguishability-obfuscation and fine-grained worst-case assumptions; those assumptions cannot be deleted here. [S2], [E3]

Attack route.

The distribution convention is kept explicit. Fix one efficient ensemble class $\mathcal D$ throughout: either the survey's polynomial-time computable distributions or its polynomial-time samplable distributions. The deductions below apply separately to either choice, provided the constructed ensemble actually belongs to that choice. No equivalence of these conventions is assumed. The average-time definition is exactly the positive-moment, correct deterministic-decider definition in the original entry. [E1]

Three routes were tested. A hard-core or minimax argument might produce a hard distribution, but would need an efficient, uniform sampler rather than an arbitrary distribution depending on a circuit. Reversible randomized encodings might spread a hard instance; a counting obstruction below shows why ordinary padding cannot spread it enough. The route pursued is a randomized oracle reduction with quantitative domination of its queries by one fixed efficient distribution. The missing construction is made explicit, and the average-time-to-circuit implication is proved rather than asserted.

Attempt: a smooth-query sufficient condition.

Lemma 52.1. Let $L=\mathsf{SAT}$ under a fixed ordinary binary encoding. Suppose there exist a language $H\in\mathsf{NP}$, an ensemble $D\in\mathcal D$, a uniform polynomial-time randomized oracle machine $R$, and polynomially bounded functions $q(n),C(n),m(n)$, with $m(n)\ge1$, such that for every $x\in\{0,1\}^n$:

1. With the exact oracle for $H$, $R^H(x)$ is correct with probability at least $5/6$; it issues at most $q(n)$ queries, all of length $m(n)$.
2. If $Q_{x,j}(S)$ is the probability that the $j$th query is issued and belongs to $S$, along that exact-oracle computation, then \begin{equation}\label{wsref-0-72-61-3a-33-30-30-30-36-36-39-38-3a-64-6f-6d-69-6e-61-74-69-6f-6e} Q_{x,j}(S)\le C(n)D_{m(n)}(S) \quad\text{for every }S\subseteq\{0,1\}^{m(n)}. \end{equation}

Here $Q_{x,j}$ may be a subprobability measure because a computation may halt before making its $j$th query. Queries may be adaptive. The common query length is part of this sufficient condition, not an assertion that every reduction can be put into this form.

If $(H,D)\in\mathsf{AvgP}$, then $L\in\mathsf{BPP}$ and hence $\mathsf{NP}\subseteq\mathsf{P/poly}$.

Proof. Let $A$ be a correct total deterministic decider for $H$ and choose $\varepsilon>0$ and a polynomial upper bound $M$ such that \[ {\mathbb{E}}_{y\sim D_m}T_A(y)^\varepsilon\le M(m). \] For length $n$, choose a polynomially bounded integer timeout $\tau(n)$ large enough that \begin{equation}\label{wsref-0-72-61-3a-33-30-30-30-36-36-39-38-3a-74-69-6d-65-6f-75-74} \tau(n)^\varepsilon\ge 12q(n)C(n)M(m(n)). \end{equation} Such a polynomial bound exists even if $\varepsilon$ is small; its degree may depend on the fixed algorithm $A$. The construction is existential and does not purport to recover this moment exponent from the code of $A$. Simulate $R$ using $A$ on each query, but abort with an arbitrary answer if a call exceeds $\tau(n)$ steps. Markov's inequality and (ra:30006698:domination) give \[ Q_{x,j}\{y:T_A(y)>\tau(n)\} \le\frac{C(n)M(m(n))}{\tau(n)^\varepsilon}. \] Couple the simulation and the exact-oracle run using the same random bits. Before the first timeout all returned answers are correct, so all queries agree with those on the exact computation path. Thus, even for adaptive queries, a union bound along that path shows \[ \Pr(\text{some timeout})\le\frac1{12}. \] There is no need to assume domination after conditioning on a particular history. The total error is at most $1/6+1/12=1/4$, and the running time is polynomial in $n$. This proves $L\in\mathsf{BPP}$.

For completeness, the nonuniform conclusion can be obtained directly. Repeat independently $O(n+1)$ times and take a majority, reducing the error on each length-$n$ input below $2^{-n-1}$. The expected number of wrong answers, summed over all $2^n$ inputs, is less than $1/2$. Some fixed choice of the polynomially many random bits is therefore correct on every input of that length. Hardwiring those bits and unrolling the polynomial-time computation gives a polynomial-size circuit. The choice need not be computable uniformly, which is precisely what $\mathsf{P/poly}$ allows. Composing with the usual polynomial-time reductions to SAT gives the conclusion for all of NP. $\square$

Consequently, constructing $R,H,D$ with these properties would prove, for the fixed convention $\mathcal D$, \begin{equation}\label{wsref-0-72-61-3a-33-30-30-30-36-36-39-38-3a-63-6f-6e-64-69-74-69-6f-6e-61-6c} \mathsf{DistNP}_{\mathcal D}\subseteq\mathsf{AvgP} \ \Longrightarrow\ \mathsf{NP}\subseteq\mathsf{P/poly}. \end{equation} The contrapositive is the entry's target for that convention. The theorem has not supplied the reduction; all of its unresolved mathematical content is in the existence of the per-input smooth encoding and oracle computation.

Attempt: obstruction to reversible smoothing.

Lemma 52.2 (list-decoding obstruction). For each $n$ let $K(x;r)$ be a random encoding of each $x\in\{0,1\}^n$, with output law $Q_x$ on a finite set $Y$. Suppose $Q_x\le C D$ for one probability law $D$ independent of $x$. Suppose also that each $y\in Y$ has a decoding list $\mathcal L(y)\subseteq\{0,1\}^n$ of size at most $\ell$, and \[ \Pr_r\{x\in\mathcal L(K(x;r))\}\ge1-\eta \quad\text{for every }x. \] Then \begin{equation}\label{wsref-0-72-61-3a-33-30-30-30-36-36-39-38-3a-6c-69-73-74-62-6f-75-6e-64} C\ell\ge (1-\eta)2^n. \end{equation} This is information-theoretic; it does not require that the decoder be computable.

Proof. Set $S_x=\{y:x\in\mathcal L(y)\}$. The hypotheses imply $1-\eta\le Q_x(S_x)\le C D(S_x)$. Summing over $x$, with only finite sums, gives \[ (1-\eta)2^n\le C\sum_y D(y)|\mathcal L(y)|\le C\ell. \] This proves the claim. $\square$

In particular, a perfectly reversible encoding has $\ell=1$, $\eta=0$ and requires $C\ge2^n$. Appending uniformly random padding to $x$ does not evade this obstruction. For $K(x;r)=(x,r)$ with $r\in\{0,1\}^k$ and uniform $D$ on all $n+k$ bits, the likelihood ratio on its support is exactly $2^n$. The distribution obtained after also averaging $x$ uniformly is perfectly uniform; this nevertheless says nothing useful about a fixed worst-case input. This is the precise quantifier error in the proposed padding argument.

The obstruction does not prohibit every multiple-query strategy. For example, $r$ and $x\mathbin{\oplus}r$ are individually uniform while the pair determines $x$. The decoding information is in their joint law, not in a short list from either marginal. This observation suggests secret-sharing-like correlated queries as a design space, but it supplies no NP language $H$ whose oracle answers recover SAT. Replacing the bits by a witness-sensitive verifier is the missing computational step, and it cannot simply be postulated as a self-reducibility property of SAT.

Stress test and dependencies.

First, the argument did not replace an average-time moment by a fixed polynomial running-time bound on every input. The timeout and its error were explicitly accounted for. It also did not replace a correct average-time algorithm by an arbitrary heuristic: correctness before a timeout is essential to the coupling proof.

Second, a worst-case circuit lower bound does not automatically produce an efficiently samplable hard distribution. Even an assertion that for every circuit there is a distribution exposing an error would have the wrong quantifier order, and a minimax distribution would still need an efficient uniform description. Neither Lemma 52.1 nor Lemma 52.2 supplies that description.

Third, the nonadaptive version of the proposed reduction is not a way around the known barrier. If an oracle differs from $H$ on a set of $D$-mass at most $1/(12qC)$, the same union bound makes the reduction robust against those errors. In the nonadaptive samplable setting this places it in the scope of the Bogdanov--Trevisan obstruction and would force the corresponding $\mathsf{coNP/poly}$ containment for SAT, with polynomial-hierarchy collapse consequences. Adaptivity is retained here, but merely allowing it is not evidence that the required reduction exists. [E1], [E2]

Finally, the only implication proved here is the conditional (ra:30006698:conditional). It does not prove $\mathsf P\ne\mathsf{NP}$, does not construct one-way functions, and does not identify deterministic average-time hardness with randomized heuristic hardness. In particular, the July 2026 gap-version distinction cannot be erased by changing the names of the classes. [E4]

Outcome.

Outcome: Conditional reduction.

A complete proof was given that a per-input polynomial-domination oracle reduction would turn the entry's average-time easiness assumption into polynomial-size circuits for NP. A separate proved counting lemma rules out reversibly decodable, polynomial-list-size encodings as a way of obtaining that domination. These are sufficient-condition and obstruction lemmas, not a construction of the needed reduction, and their originality in the literature has not been established.

To resolve the target by this route one must construct such a reduction for an NP-complete language with one ensemble in the selected efficient class, or replace the domination mechanism by a different rigorously proved conversion. No such construction or counterexample to the worst-case/average-case implication was obtained in this batch.

Sources

• S1 A. Bogdanov, L. Trevisan, SIAM J. Comput. 36$4$:1119-1159, 2006. https://doi.org/10.1137/050634629. Catalogue formulation source.
• S2 Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions. https://eccc.weizmann.ac.il/report/2025/072/download. Catalogue research/status reference; not a proof endorsement.
• S3 Hardness of Computing Nondeterministic Kolmogorov Complexity. https://eccc.weizmann.ac.il/report/2025/203/. Catalogue research/status reference; not a proof endorsement.
• E1 Andrej Bogdanov and Luca Trevisan, Average-Case Complexity, Foundations and Trends in Theoretical Computer Science 2 $2006$, 1--106. https://andrejb.net/pubs/average-now.pdf. Added primary source: Definitions of distributional problems and average-polynomial time. Consulted 24 September 2026.
• E2 Andrej Bogdanov and Luca Trevisan, On Worst-Case to Average-Case Reductions for NP Problems, SIAM Journal on Computing 36$4$ $2006$, 1119--1159, DOI 10.1137/S0097539705446974. See also the precise nonadaptive formulation in Theorem 7.5 of [E1]. https://doi.org/10.1137/S0097539705446974. Added research source: Corrected identifier for the paper intended by [S1]; nonadaptive reduction barrier. The original [S1] is preserved. Consulted 24 September 2026.
• E3 Rahul Ilango and Alex Lombardi, Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions, ECCC TR25-072 $2025$, abstract and stated cryptographic hypotheses. https://eccc.weizmann.ac.il/report/2025/072/. Added research source: The additional obfuscation and fine-grained assumptions are retained, not treated as consequences of the target premise. Consulted 24 September 2026.
• E4 Jinqiao Hu, Zhenjian Lu and Igor Oliveira, Hardness of Computing Nondeterministic Kolmogorov Complexity, ECCC TR25-203, revision 2, 5 July 2026, Section 1.2.3 and Appendix B, including Corollary 59. https://eccc.weizmann.ac.il/report/2025/203/revision/2/download. Added research source: Recent meta-complexity implications and the remaining gap-version obstacle; not identified with the deterministic average-time assertion. Consulted 24 September 2026.