ECCC-Report TR15-198https://eccc.weizmann.ac.il/report/2015/198Comments and Revisions published for TR15-198en-usSun, 13 Mar 2016 15:12:28 +0200
Revision 1
| Limits of Minimum Circuit Size Problem as Oracle |
Shuichi Hirahara,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2015/198#revision1The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a major open problem in computational complexity.
In this paper, we provide strong evidences that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of black-box reduction to MCSP, which captures all the currently known reductions. We say that a reduction to MCSP is black-box if the reduction can be generalized to a reduction to MCSP$^A$ for any oracle A, where MCSP$^A$ denotes an oracle version of MCSP. We prove that essentially no language is reducible to MCSP via a polynomial-time Turing reduction in a black-box way. We also show that the class of languages reducible to MCSP via a black-box randomized reduction that makes at most one query is contained in AM and coAM. Thus, NP-hardness of MCSP cannot be established via such black-box reductions unless the polynomial hierarchy collapses.
We also extend the previous results to the case of more general reductions: We prove that establishing NP-hardness of MCSP via a polynomial-time nonadaptive reduction implies ZPP $\neq$ EXP, and that establishing NP-hardness of approximating circuit complexity via a polynomial-time Turing reduction also implies ZPP $\neq$ EXP. Along the way, we prove that approximating Levin's Kolmogorov complexity is provably not EXP-hard under a polynomial-time Turing reduction, which is of independent interest.Sun, 13 Mar 2016 15:12:28 +0200https://eccc.weizmann.ac.il/report/2015/198#revision1
Paper TR15-198
| Limits of Minimum Circuit Size Problem as Oracle |
Shuichi Hirahara,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2015/198The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a major open problem in computational complexity.
In this paper, we provide strong evidences that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of black-box reduction to MCSP, which captures all the currently known reductions. We say that a reduction to MCSP is black-box if the reduction can be generalized to a reduction to MCSP$^A$ for any oracle A, where MCSP$^A$ denotes an oracle version of MCSP. We prove that essentially no language is reducible to MCSP via a polynomial-time Turing reduction in a black-box way. We also show that the class of languages reducible to MCSP via a black-box randomized reduction that makes at most one query is contained in AM and coAM. Thus, NP-hardness of MCSP cannot be established via such black-box reductions unless the polynomial hierarchy collapses.
We also extend the previous results to the case of more general reductions: We prove that establishing NP-hardness of MCSP via a polynomial-time nonadaptive reduction implies ZPP $\neq$ EXP, and that establishing NP-hardness of approximating circuit complexity via a polynomial-time Turing reduction also implies ZPP $\neq$ EXP. Along the way, we prove that approximating Levin's Kolmogorov complexity is provably not EXP-hard under a polynomial-time Turing reduction, which is of independent interest.Tue, 08 Dec 2015 22:36:33 +0200https://eccc.weizmann.ac.il/report/2015/198