Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
作者： Ruiwen Chen , Rahul Santhanam
DOI: 10.1007/978-3-319-24318-4_4
关键词: PSPACE 、 Maximum satisfiability problem 、 Algorithm 、 Omega 、 Exponential space 、 Physics 、 Sparse approximation
摘要: We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-k-CSP. For with n variables cn clauses (constraints), we running in time \({{\mathrm{poly}}}(n)\cdot 2^{n(1-\mu )}\) for \(\mu = \Omega (\frac{1}{c} )\) polynomial space MAX-k-SAT, \(\mu (\frac{1}{\sqrt{c}} exponential (\frac{1}{ck^2} MAX-k-CSP, \(\mu (\frac{1}{\sqrt{ck^3}}
core.ac.uk
springer.com
ed.ac.uk
sci-hub.st 参考文章(19)
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh, An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas mathematical foundations of computer science. pp. 165- 176 ,(2014) , 10.1007/978-3-662-44465-8_15
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction theory and applications of satisfiability testing. pp. 32- 47 ,(2014) , 10.1007/978-3-319-09284-3_4
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, The Complexity of Satisfiability of Small Depth Circuits Parameterized and Exact Computation. pp. 75- 85 ,(2009) , 10.1007/978-3-642-11269-0_6
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, Noam Nisan, The effect of random restrictions on formula size Random Structures and Algorithms. ,vol. 4, pp. 121- 133 ,(1993) , 10.1002/RSA.3240040202
Alexander D Scott, Gregory B Sorkin, None, Linear-programming design and analysis of fast algorithms for Max 2-CSP Discrete Optimization. ,vol. 4, pp. 260- 287 ,(2007) , 10.1016/J.DISOPT.2007.08.001
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
Alexander S. Kulikov, Konstantin Kutzkov, New Bounds for MAX-SAT by Clause Learning Computer Science – Theory and Applications. pp. 194- 204 ,(2007) , 10.1007/978-3-540-74510-5_21
Alexander Golovnev, Konstantin Kutzkov, New exact algorithms for the 2-constraint satisfaction problem Theoretical Computer Science. ,vol. 526, pp. 18- 27 ,(2014) , 10.1016/J.TCS.2014.01.010
Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider, A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 479- 488 ,(2013) , 10.1109/FOCS.2013.58