Average-case hardness of NP from exponential worst-case hardness assumptions

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:

DistNP ⊆ Avg P P. Here, Avg P P denotes P-computable average-case polynomial time, which interpolates average-case polynomial-time and worstcase polynomial-time. We complement this result by showing that DistPH ⊆ AvgP if and only if DistPH ⊆ 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.

time if, in addition to the above definition of AvgP, the function t : 0, 1 * → N is computable in polynomial time. The class of distributional problems that admit P-computable average-case polynomial-time algorithms is denoted by Avg P P. (Equivalent definitions of AvgP and Avg P P are errorless heuristic scheme and P-bounded failure heuristic scheme, respectively; see Section 9.) For example, for the HamiltonianPath problem and the Erdős-Rényi random graph G(n, 1/2), it is not difficult to observe that the distributional problem (HamiltonianPath, G(n, 1/2) n∈N ) is in Avg P P using the heuristic algorithms of [Tho89] (see Appendix B).

An average-case analogue of NP is denoted by DistNP, which consists of distributional problems (L, D) such that L ∈ NP and D ∈ PSamp, where PSamp is the class of polynomial-time samplable distributions. In other words, we focus on analyzing the average-case complexity of NP with respect to the distributions from which a random instance can be efficiently generated. More generally, we define Dist(C) to be C × PSamp for any complexity class C.

A central open question in average-case complexity theory is to connect the average-case hardness of NP to the worst-case hardness of NP:

This is arguably one of the four central questions 3 in complexity theory and cryptography. In his influential work, Impagliazzo [Imp95] classified the ultimate consequences of complexity theory into five possible scenarios. Excluding any one of the scenarios is considered an important milestone. Open Question 1.1 and its variants correspond to excluding Heuristica (i.e., a world where NP is hard in the worst case but easy on average) from the five possible worlds.

Currently, a question much weaker than Open Question 1.1 is open. A frontier question along the lines of Open Question 1.1 is to prove the average-case hardness of the polynomial-time hierarchy (PH) assuming the existence of an exponentially hard problem in UP.