SAT Algorithms from Shrinkage.
Avishay Tal · Electronic colloquium on computational complexity · 2015
We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula F of size at most n3−16e in time 2n−n e · poly(n), for any small constant e > 0. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et al. (CCC, 2014). Our result uses the tight “shrinkage in expectation” result of de Morgan formulas by Hastad (SICOMP, 1998) as a black-box, and improves upon the result of Chen et al. (MFCS, 2014) that gave deterministic counting algorithms for de Morgan formulas of size at most n. Our algorithm generalizes to other bases of Boolean gates giving a 2n−n e · poly(n) time counting algorithm for formulas of size at most nΓ+1−O(e), where Γ is the shrinkage exponent for formulas using gates from the basis. ∗Weizmann Institute of Science, Rehovot, Israel. [email protected]. Supported by an Adams Fellowship of the Israel Academy of Sciences and Humanities, by an ISF grant and by the I-CORE Program of the Planning and Budgeting Committee. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 114 (2015)