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.