Hirahara, Shuichi ;
Watanabe, Osamu
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 BPPTuring reduction (Allender and Das, 2014), whereas establishing NPhardness of MCSP via a polynomialtime manyone reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP != EXP, which is a major open problem in computational complexity.
In this paper, we provide strong evidence that current techniques cannot establish NPhardness of MCSP, even under polynomialtime Turing reductions or randomized reductions: Specifically, we introduce the notion of oracleindependent reduction to MCSP, which captures all the currently known reductions. We say that a reduction to MCSP is oracleindependent 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 no language outside P is reducible to MCSP via an oracleindependent polynomialtime Turing reduction. We also show that the class of languages reducible to MCSP via an oracleindependent randomized reduction that makes at most one query is contained in AM intersect coAM. Thus, NPhardness of MCSP cannot be established via such oracleindependent reductions unless the polynomial hierarchy collapses.
We also extend the previous results to the case of more general reductions: We prove that establishing NPhardness of MCSP via a polynomialtime nonadaptive reduction implies ZPP != EXP, and that establishing NPhardness of approximating circuit complexity via a polynomialtime Turing reduction also implies ZPP != EXP. Along the way, we prove that approximating Levin's Kolmogorov complexity is provably not EXPhard under polynomialtime Turing reductions, which is of independent interest.
BibTeX  Entry
@InProceedings{hirahara_et_al:LIPIcs:2016:5842,
author = {Shuichi Hirahara and Osamu Watanabe},
title = {{Limits of Minimum Circuit Size Problem as Oracle}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {18:118:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5842},
URN = {urn:nbn:de:0030drops58426},
doi = {10.4230/LIPIcs.CCC.2016.18},
annote = {Keywords: minimum circuit size problem, NPcompleteness, randomized reductions, resourcebounded Kolmogorov complexity, Turing reductions}
}
2016
Keywords: 

minimum circuit size problem, NPcompleteness, randomized reductions, resourcebounded Kolmogorov complexity, Turing reductions 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 