Constant Depth Formula and Partial Function Versions of MCSP are Hard
Rahul Ilango · 2020
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 N P-hard under quasipolynomial-time 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(n1/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 subexponential-sized circuits computing SAT, the lower bound statements used to prove the correctness of our reductions cannot be (P/poly)-recognizable.