Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-138 | 10th August 2018 12:39

Non-black-box Worst-case to Average-case Reductions within NP

RSS-Feed

Abstract:

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 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 outside coNP (unless Random 3SAT is easy for coNP algorithms) 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 $\widetilde{O}(\sqrt{k})$ if its average-case version admits an errorless heuristic polynomial-time algorithm. (The converse direction also holds under a plausible derandomization assumption.) We also show that, given a truth table of size $2^n$, approximating the minimum circuit size within a factor of $2^{(1 - \epsilon) n}$ is in BPP for some constant $\epsilon > 0$ if and only if its average-case version is easy.

Based on our results, we propose a research program for excluding Heuristica, i.e., establishing an equivalence between the worst-case and average-case hardness of NP through the lens of MINKT or the Minimum Circuit Size Problem (MCSP).



ISSN 1433-8092 | Imprint