NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions

Whether the Minimum Circuit Size Problem (MCSP) is NP-hard or not is a long-standing open question. Indeed, Levin delayed the publication of his fundamental work on the theory of NP-completeness because he hoped to prove NP-completeness of MCSP.

In this paper, we present the first plausible assumptions under which MCSP is NP-hard. Specifically, we prove that MCSP is NP-hard under deterministic quasi-polynomial-time nonadaptive reductions, assuming:

• subexponentially-secure non-interactive witness indistinguishable proof systems for SAT exist, • coNP requires subexponential-size non-deterministic circuits, and • P NP /poly requires circuits of size Ω(2 n /n). This is arguably the first evidence that MCSP is not in coNP, which indicates that there is no short proof that witnesses the hardness of a function.