We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence:
DistPH is contained in AvgP (i.e., PH is easy on average) if and only if GapMINKT(PH) is in P.
In fact, our equivalence is significantly broad: A number of statements on several fundamental notions of complexity theory, such as errorless and one-sided-error average-case complexity, sublinear-time-bounded and polynomial-time-bounded Kolmogorov complexity, and PH-computable hitting set generators, are all shown to be equivalent.
Our equivalence provides fundamentally new proof techniques for analyzing average-case complexity through the lens of *meta-complexity* of time-bounded Kolmogorov complexity and resolves, as immediate corollaries, questions of equivalence among different notions of average-case complexity of PH: low success versus high success probabilities (i.e., a hardness amplification theorem for DistPH against uniform algorithms) and errorless versus one-sided-error average-case complexity of PH.
Our results are based on a sequence of new technical results that further develops the proof techniques of the author's previous work on the non-black-box worst-case to average-case reduction and unexpected hardness results for Kolmogorov complexity (FOCS'18, CCC'20, ITCS'20, STOC'20). Among other things, we prove the following.
1. If GapMINKT(NP) is in P, then P = BPP.
At the core of the proof is a new black-box hitting set generator construction whose reconstruction algorithm uses few random bits, which also improves the approximation quality of the non-black-box worst-case to average-case reduction without using a pseudorandom generator.
2. If GapMINKT(PH) is in P, then DistPH is contained in AvgBPP = AvgP.
3. If MINKT(PH) is easy on a 1/poly(n)-fraction of inputs, then GapMINKT(PH) is in P.
This improves the error tolerance of the previous non-black-box worst-case to average-case reduction.
