Guided Search and a Faster Deterministic Algorithm for 3-SAT

作者： Dominik Scheder

DOI: 10.1007/978-3-540-78773-0_6

关键词: Algorithm 、 Mathematical optimization 、 Deterministic algorithm 、 Running time 、 Mathematics

摘要: Most deterministic algorithms for NP-hard problems are splitting algorithms: They split a problem instance into several smaller ones, which they solve recursively. Often, the …

参考文章(10)

David Eppstein, Richard Beigel, 3-Coloring in time O(1.3446n): a no-MIS algorithm ,(2000)

Tobias Brueggemann, Walter Kern, An improved local search algorithm for 3-SAT cologne twente workshop on graphs and combinatorial optimization. ,vol. 17, pp. 69- 73 ,(2004) , 10.1016/J.ENDM.2004.03.021

B. Monien, E. Speckenmeyer, Solving satisfiability in less than 2n steps Discrete Applied Mathematics. ,vol. 10, pp. 287- 295 ,(1985) , 10.1016/0166-218X(85)90050-2

Donald Loveland, George Logemann, Martin Davis, A machine program for theorem-proving ,(2011)

Martin Davis, Hilary Putnam, A Computing Procedure for Quantification Theory Journal of the ACM. ,vol. 7, pp. 201- 215 ,(1960) , 10.1145/321033.321034

Tobias Brueggemann, Walter Kern, An improved deterministic local search algorithm for 3-SAT Theoretical Computer Science. ,vol. 329, pp. 303- 313 ,(2004) , 10.1016/J.TCS.2004.08.002

R. Beigel, D. Eppstein, 3-coloring in time 0(1.3446/sup n/): a no-MIS algorithm foundations of computer science. pp. 444- 452 ,(1995) , 10.1109/SFCS.1995.492575

Evgeny Dantsin, Andreas Goerdt, Edward A Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, Uwe Schöning, A deterministic (2 - 2/( k + 1)) n algorithm for k -SAT based on local search Theoretical Computer Science. ,vol. 289, pp. 69- 83 ,(2002) , 10.1016/S0304-3975(01)00174-8

David Eppstein, Richard Beigel, 3-Coloring in Time O(1.3446 n ): A No-MIS Algorithm. foundations of computer science. pp. 444- 452 ,(1995)

Daniel Rolf, Improved Bound for the PPSZ/Schoning-Algorithm for 3-SAT Journal on Satisfiability, Boolean Modeling and Computation. ,vol. 1, pp. 111- 122 ,(2006) , 10.3233/SAT190005