Revised: February 15, 2017

Published: June 30, 2017

**Keywords:**circuit lower bounds, reductions, NP-completeness, projections, minimum circuit size problem

**ACM Classification:**F.2.3, F.1.3

**AMS Classification:**68Q15, 68Q17

**Abstract:**
[Plain Text Version]

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 \Ppoly$ 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 \Ppoly$, 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 \Ppoly$.

A preliminary version of this paper appeared in the Proceedings of the 30th IEEE Conference on Computational Complexity, 2015.