License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2015.365
URN: urn:nbn:de:0030-drops-50745
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5074/
Murray, Cody D. ;
Williams, R. Ryan
On the (Non) NP-Hardness of Computing Circuit Complexity
Abstract
The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of its kind, MCSP is not known to be NP-hard, yet an efficient algorithm for this problem also seems very unlikely: for example, MCSP in P would imply there are no pseudorandom functions.
Although most NP-complete problems are complete under strong "local" reduction notions such as poly-logarithmic time projections, we show that MCSP is provably not NP-hard under O(n^(1/2-epsilon))-time projections, for every epsilon > 0. We prove that the NP-hardness of MCSP under (logtime-uniform) AC0 reductions would imply extremely strong lower bounds: NP \not\subset P/poly and E \not\subset i.o.-SIZE(2^(delta * n)) for some delta > 0 (hence P = BPP also follows). We show that even the NP-hardness of MCSP under general polynomial-time reductions would separate complexity classes: EXP != NP \cap P/poly, which implies EXP != ZPP. These results help explain why it has been so difficult to prove that MCSP is NP-hard.
We also consider the nondeterministic generalization of MCSP: the Nondeterministic Minimum Circuit Size Problem (NMCSP), where one wishes to compute the nondeterministic circuit complexity of a given function. We prove that the Sigma_2 P-hardness of NMCSP, even under arbitrary polynomial-time reductions, would imply EXP \not\subset P/poly.
BibTeX - Entry
@InProceedings{murray_et_al:LIPIcs:2015:5074,
author = {Cody D. Murray and R. Ryan Williams},
title = {{On the (Non) NP-Hardness of Computing Circuit Complexity}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {365--380},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-81-1},
ISSN = {1868-8969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5074},
URN = {urn:nbn:de:0030-drops-50745},
doi = {10.4230/LIPIcs.CCC.2015.365},
annote = {Keywords: circuit lower bounds, Minimum Circuit Size Problem, NP-completeness, projections, Reductions}
}
|
Keywords: |
|
circuit lower bounds, Minimum Circuit Size Problem, NP-completeness, projections, Reductions |
|
Collection: |
|
30th Conference on Computational Complexity (CCC 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
06.06.2015 |
