Non-Black-Box Worst-Case to Average-Case Reductions Within \(NP\)

This is the authors' abstract. We don't add key points for this paper.

.There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of \(NP\). Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside \(coNP/poly\) to a distributional \(NP\) problem. This paper overcomes the barrier. We present the first non-black-box worst-case to average-case reduction from a problem conjectured to be outside \(coNP/poly\) to a distributional \(NP\) problem. Specifically, we consider the minimum time-bounded Kolmogorov complexity problem (MINKT) and prove that there exists a zero-error randomized polynomial-time algorithm approximating the minimum time-bounded Kolmogorov complexity \(k\) within an additive error \({O}(√k)\) if its average-case version admits an errorless heuristic polynomial-time algorithm. We observe that the approximation version of MINKT is Random 3SAT-hard, and more generally it is harder than avoiding any polynomial-time computable hitting set generator that extends its seed of length \(n\) by \({ω }(√n)\), which provides strong evidence that the approximation problem is outside \(coNP/poly\) and thus our reductions are non-black-box. Our reduction can be derandomized at the cost of the quality of the approximation. We also show that, given a truth table of size \(2^n\), approximating the minimum circuit size within a factor of \(2(1 - ε ) n\) is in \(BPP\) for some constant \(ε > 0\) iff its average-case version is easy. Our results can be seen as a new approach for excluding Heuristica. In particular, proving \(NP\)-hardness of the approximation versions of MINKT or the minimum circuit size problem is sufficient for establishing an equivalence between the worst-case and average-case hardness of \(NP\).