Volume 13 (2017) Article 4 pp. 1-22

On the (Non) NP-Hardness of Computing Circuit Complexity

by Cody D. Murray and R. Ryan Williams

Received: October 30, 2015
Revised: February 15, 2017
Published: June 30, 2017

$\newcommand{\MCSP}{\mathrm{MCSP}} \newcommand{\NMCSP}{\mathrm{NMCSP}} \def \AC {{\sf AC}} \def \poly {\mathrm{poly}} \def \P {{\sf P}} \def \ZPP {{\sf ZPP}} \def \EXP {{\sf EXP}} \def \NP {{\sf NP}} \def \eps {{\varepsilon}} \def \E {{\sf E}} \def \SIZE {{\sf SIZE}} \def \BPP {{\sf BPP}} \def \Ppoly {{\P/\poly}} \def \io {\mathrm{i.o.}{\text{-}}}$

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.

DOI: 10.4086/toc.2017.v013a004

© 2017 Cody D. Murray and R. Ryan Williams
Licensed under a Creative Commons Attribution License (CC-BY)