Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
Shuichi Hirahara · SIAM Journal on Computing · 2023
Abstract. There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of [Formula: see text]. 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 [Formula: see text] to a distributional [Formula: see text] 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 [Formula: see text] to a distributional [Formula: see text] 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 [Formula: see text] within an additive error [Formula: see text] 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 [Formula: see text] by [Formula: see text], which provides strong evidence that the approximation problem is outside [Formula: see text] 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 [Formula: see text], approximating the minimum circuit size within a factor of [Formula: see text] is in [Formula: see text] for some constant [Formula: see text] iff its average-case version is easy. Our results can be seen as a new approach for excluding Heuristica. In particular, proving [Formula: see text]-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 [Formula: see text].