期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-52
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 cry ptography, 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 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 22d(n) 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 collection of lower bound statements used to prove the correctness of our reductions cannot be (P/poly)-recognizable. 2012 ACM Subject Classification Theory of computation→Circuit complexity; Theory of compu- tation→Problems, reductions and completene.
