ECCC-Report TR21-058https://eccc.weizmann.ac.il/report/2021/058Comments and Revisions published for TR21-058en-usSun, 25 Apr 2021 13:22:37 +0300
Paper TR21-058
| Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions |
Shuichi Hirahara
https://eccc.weizmann.ac.il/report/2021/058A 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.Sun, 25 Apr 2021 13:22:37 +0300https://eccc.weizmann.ac.il/report/2021/058