Theory of Computing
-------------------
Title : On the (Non) NP-Hardness of Computing Circuit Complexity
Authors : Cody D. Murray and R. Ryan Williams
Volume : 13
Number : 4
Pages : 1-22
URL : http://www.theoryofcomputing.org/articles/v013a004
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 polylogarithmic-time projections, we
show that MCSP is _provably not_ NP-hard under
$O(n^{1/2-\eps})$-time projections, for every $\eps > 0$, and is not
NP-hard under randomized $O(n^{1/5-\eps})$-time projections, for
every $\eps > 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 \neq \NP \cap P/poly, which implies EXP \neq 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.
A preliminary version of this paper appeared in the Proceedings of the
30th IEEE Conference on Computational Complexity, 2015.