Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica

Abstract

One of the central open questions in computational complexity theory is to connect worst-case hardness of NP to average-case hardness of NP. This question is well known as whether Heuristica is excluded from Impagliazzo’s five worlds. It is known that standard proof techniques that relate worst-case and average-case complexities are incapable of excluding Heuristica; thus, in order to make progress, we need to develop new proof techniques.
Recently, new worst-case to average-case connections that cannot be proved by previous proof techniques are established based on meta-complexity. Meta-complexity refers to the computational complexity of problems that themselves ask complexity. In this article, we present the emerging paradigm of “meta-computational average-case complexity,” i.e., a new approach of analyzing average-case complexity via meta-complexity of time-bounded Kolmogorov complexity.