Average case and worst case complexity linked through meta computational problems
The Gap Between Average-Case and Worst-Case Complexity
Computational Complexity
Summary
Understanding how hard problems are on average compared to their hardest cases is a big question in computer science, especially for a group of problems called the polynomial hierarchy. The authors found that connecting average-case difficulty to worst-case difficulty is actually equivalent to solving another kind of problem that deals with measuring program complexity timings. This means techniques previously thought unrelated to this main question are fundamentally tied to it. Their work narrows down where progress might come from and explains why certain types of solutions must be very sophisticated.
What this means in practice
- •For cryptography engineers: Clarify the fundamental complexity assumptions underpinning cryptographic security related to average-case hardness of polynomial hierarchy problems.
- •For complexity theorists building algorithms: Guide design of reductions and complexity analyses by showing the necessity of meta-computational perspectives for linking average and worst cases.
A theory result. No direct application yet.
Authors
Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
Abstract
Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$. Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way. We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence. Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version. Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$. Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity. We make progress by proving that the gap in running time can be eliminated in the average-case setting. Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.