Statement copy in the gpt 6 astra pro collection (CS-29)

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.