Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-058 | 21st April 2021 08:55

#### Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions

TR21-058
Authors: Shuichi Hirahara
Publication: 25th April 2021 13:22
Keywords:

Abstract:

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this question has been discussed from various perspectives based on technical barrier results, such as the limits of black-box reductions and the non-existence of worst-case hardness amplification procedures in PH.

In this paper, we overcome these barriers and resolve the open question by presenting the following main results:

1. \$UP \not\subseteq DTIME(2^{O(n / \log n)})\$ implies \$DistNP \not\subseteq AvgP\$.

2. \$PH \not\subseteq DTIME(2^{O(n / \log n)})\$ implies \$DistPH \not\subseteq AvgP\$.

3. \$NP \not\subseteq DTIME(2^{O(n / \log n)})\$ implies \$DistNP \not\subseteq Avg_P P\$.
Here, \$Avg_P P\$ denotes P-computable average-case polynomial time, which interpolates average-case polynomial-time and worst-case polynomial-time. We complement this result by showing that \$DistPH \not\subseteq AvgP\$ if and only if \$DistPH \not\subseteq Avg_P P\$.

At the core of all of our results is a new notion of universal heuristic scheme, whose running time is P-computable average-case polynomial time under every polynomial-time samplable distribution. Our proofs are based on the meta-complexity of time-bounded Kolmogorov complexity: We analyze average-case complexity through the lens of worst-case meta-complexity using a new "algorithmic" proof of language compression and weak symmetry of information for time-bounded Kolmogorov complexity.

ISSN 1433-8092 | Imprint