Revised: February 15, 2017
Published: June 30, 2017
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.