Constant Depth Formula and Partial Function Versions of MCSP are Hard

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

While Masek showed in the late 1970s that the version of MCSP for DNF formulas is NP-hard, extending this result to the case of depth-3 AND/OR formulas was open. We show that determining the minimum size of a depth-d formula computing a given Boolean function is NP-hard under quasipolynomialtime randomized reductions for all constant d ≥ 2. Our approach is based on a method to "lift" depth-d formula lower bounds to depth-(d+1). This method also implies the existence of a function with a 2 Ω d (n 1/5 ) additive gap between its depth-d and depth-(d + 1) formula complexity.

We also make progress in the case of general, unrestricted circuits. We show that the version of MCSP where the input is a partial function (represented by a string in 0, 1, ? * ) is not in P under the Exponential Time Hypothesis (ETH).

Intriguingly, we formulate a notion of lower bound statements being (P/poly)-recognizable that is closely related to Razborov and Rudich's definition of being (P/poly)constructive. We show that unless there are subexponentialsized circuits computing SAT, the lower bound statements used to prove the correctness of our reductions cannot be (P/poly)recognizable.