Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-198 | 13th March 2016 15:12

Limits of Minimum Circuit Size Problem as Oracle

RSS-Feed




Revision #1
Authors: Shuichi Hirahara, Osamu Watanabe
Accepted on: 13th March 2016 15:12
Downloads: 502
Keywords: 


Abstract:

The 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.



Changes to previous version:

Changed the term "black-box reductions" into "oracle-independent reductions". Added more intuitions to proofs. Modified the introduction.


Paper:

TR15-198 | 30th November 2015 15:34

Limits of Minimum Circuit Size Problem as Oracle


Abstract:

The 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.



ISSN 1433-8092 | Imprint