ECCC-Report TR18-138https://eccc.weizmann.ac.il/report/2018/138Comments and Revisions published for TR18-138en-usThu, 28 Feb 2019 09:41:52 +0200
Revision 1
| Non-black-box Worst-case to Average-case Reductions within NP |
Shuichi Hirahara
https://eccc.weizmann.ac.il/report/2018/138#revision1There 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 conjectured to be outside coNP 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. 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 $\widetilde{\omega}(\sqrt{n})$, which provides strong evidence that the approximation problem is outside coNP 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 - \epsilon) n}$ is in BPP for some constant $\epsilon > 0$ if and only if 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 (MCSP) is sufficient for establishing an equivalence between the worst-case and average-case hardness of NP.
Thu, 28 Feb 2019 09:41:52 +0200https://eccc.weizmann.ac.il/report/2018/138#revision1
Paper TR18-138
| Non-black-box Worst-case to Average-case Reductions within NP |
Shuichi Hirahara
https://eccc.weizmann.ac.il/report/2018/138There 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).
Fri, 10 Aug 2018 13:07:32 +0300https://eccc.weizmann.ac.il/report/2018/138