An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
作者： Ruiwen Chen , Valentine Kabanets , Nitin Saurabh
DOI: 10.1007/978-3-662-44465-8_15
关键词:
摘要: We give a deterministic #SAT algorithm for de Morgan formulas of size up to n 2.63, which runs in time \(2^{n-n^{\Omega(1)}}\). This improves upon the [3], has similar running but works only less than 2.5.
springer.com
core.ac.uk
sci-hub.st 参考文章(17)
Pavel Pudlák, Ramamohan Paturi, Francis Zane, Satisfiability Coding Lemma. Chicago Journal of Theoretical Computer Science. ,vol. 1999, ,(1999)
Rahul Santhanam, Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. pp. 183- 192 ,(2010) , 10.1109/FOCS.2010.25
Russell Impagliazzo, Raghu Meka, David Zuckerman, Pseudorandomness from Shrinkage 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 111- 119 ,(2012) , 10.1109/FOCS.2012.78
Russell Impagliazzo, Noam Nisan, The effect of random restrictions on formula size Random Structures and Algorithms. ,vol. 4, pp. 121- 133 ,(1993) , 10.1002/RSA.3240040202
Luca Trevisan, Tongke Xue, A Derandomized Switching Lemma and an Improved Derandomization of AC0 2013 IEEE Conference on Computational Complexity. pp. 242- 247 ,(2013) , 10.1109/CCC.2013.32
Johan HÅ stad, The Shrinkage Exponent of de Morgan Formulas is 2 SIAM Journal on Computing. ,vol. 27, pp. 48- 64 ,(1998) , 10.1137/S0097539794261556
Ryan Williams, Improving exhaustive search implies superpolynomial lower bounds Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10. pp. 231- 240 ,(2010) , 10.1145/1806689.1806723
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman, Mining Circuit Lower Bound Proofs for Meta-algorithms 2014 IEEE 29th Conference on Computational Complexity (CCC). pp. 262- 273 ,(2014) , 10.1109/CCC.2014.34
Ilan Komargodski, Ran Raz, Average-case lower bounds for formula size Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13. pp. 171- 180 ,(2013) , 10.1145/2488608.2488630
Ilan Komargodski, Ran Raz, Avishay Tal, Improved Average-Case Lower Bounds for DeMorgan Formula Size 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 588- 597 ,(2013) , 10.1109/FOCS.2013.69