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       : https://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.