Shuichi Hirahara: Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions

Abstract:

Basing the average-case hardness of NP on the worst-case hardness of NP is a long-standing and central open question in complexity theory, which is known as the question of excluding Heuristica from Impagliazzo’s five possible worlds.  It has been a long-standing open question to base the average-case hardness of PH on the exponential worst-case hardness of UP, and a large body of research has been devoted to explaining why standard proof techniques fail to resolve the open question.

In this work, we develop new proof techniques and resolve the open question.  We prove that if UP is not in DTIME(2^{O(n/log n)}), then NP is hard on average.  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 by using several new notions such as universal heuristic scheme and P-computable average-case polynomial-time.