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.