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-\varepsilon})$-time projections, for every $\varepsilon > 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$ io-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$.