Murray, Cody D. ;
Williams, R. Ryan
On the (Non) NPHardness 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 NPhard, 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 NPcomplete problems are complete under strong "local" reduction notions such as polylogarithmic time projections, we show that MCSP is provably not NPhard under O(n^(1/2epsilon))time projections, for every epsilon > 0. We prove that the NPhardness of MCSP under (logtimeuniform) 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 NPhardness of MCSP under general polynomialtime 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 NPhard.
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 Phardness of NMCSP, even under arbitrary polynomialtime 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) NPHardness of Computing Circuit Complexity}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {365380},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5074},
URN = {urn:nbn:de:0030drops50745},
doi = {10.4230/LIPIcs.CCC.2015.365},
annote = {Keywords: circuit lower bounds, Minimum Circuit Size Problem, NPcompleteness, projections, Reductions}
}
06.06.2015
Keywords: 

circuit lower bounds, Minimum Circuit Size Problem, NPcompleteness, projections, Reductions 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

06.06.2015 