Paper Info
Title
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity
Abstract
We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PH</sup> , 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) ⇐⇒ GapMINKT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PH</sup> ∈ 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) GapMINKT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">NP</sup> ∈ 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 nonblack-box worst-case to average-case reduction without using a pseudorandom generator. 2) GapMINKT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PH</sup> ∈ P implies DistPH ⊆ AvgBPP = AvgP. 3) If MINKT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PH</sup> ∈ P is easy on a 1/poly(n)-fraction of inputs, then GapMINKT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PH</sup> ∈ P. This improves the error tolerance of the previous non-black-box worst-case to average-case reduction. The full version of the paper is available on ECCC.
Year
DOI
Venue
2020
10.1109/FOCS46700.2020.00014
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
Volume
average-case complexity,meta-complexity,Kolmogorov complexity,polynomial-time hierarchy,hitting set generator,hardness amplification,pseudorandomness
Conference
27
ISSN
ISBN
Citations 
1523-8288
978-1-7281-9622-0
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Shuichi Hirahara137.48