Paper Info
Title
Average-case hardness of NP from exponential worst-case hardness assumptions
Abstract
ABSTRACTA 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 ⊈DTIME(2O(n / logn)) implies DistNP ⊈AvgP. 2. PH ⊈DTIME(2O(n / logn)) implies DistPH ⊈AvgP. 3. NP ⊈DTIME(2O(n / logn)) implies DistNP ⊈AvgP P. Here, AvgP 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 ⊈AvgP if and only if DistPH ⊈AvgP 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.
Year
DOI
Venue
2021
10.1145/3406325.3451065
ACM Symposium on Theory of Computing
DocType
Volume
Citations 
Conference
28
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Shuichi Hirahara137.48