Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

摘要

We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKTPH, 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 ? AvgP ( i.e., PH is easy on average ) ?? GapMINKTPH ∈ 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 PHcomputable 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 averagecase 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. GapMINKTNP ∈ P implies 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. GapMINKTPH ∈ P implies DistPH ? AvgBPP = AvgP. 3. If MINKTPH is easy on a 1/poly(n)-fraction of inputs, then GapMINKTPH ∈ P. This improves the error tolerance of the previous non-black-box worst-case to average-case reduction.