A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search

被引:94
作者
Dantsin, E
Goerdt, A
Hirsch, EA
Kannan, R
Kleinberg, J
Papadimitriou, C
Raghavan, P
Schöning, U
机构
[1] VA Steklov Math Inst, St Petersburg 191011, Russia
[2] Univ Manchester, Dept Comp Sci, Manchester M13 9PL, Lancs, England
[3] TU Chemnitz, Fak Informat, D-09107 Chemnitz, Germany
[4] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA
[5] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA
[6] Univ Calif Berkeley, Div Comp Sci, Berkeley, CA 94720 USA
[7] Ver Inc, Sunnyvale, CA 94089 USA
[8] Univ Ulm, Abt Theoret Infomat, D-89069 Ulm, Germany
基金
英国工程与自然科学研究理事会; 美国国家科学基金会; 俄罗斯基础研究基金会;
关键词
D O I
10.1016/S0304-3975(01)00174-8
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schoning (1999) proved that a close algorithm for k-SAT takes time (2 - 2/k)(n) up to a polynomial factor. This is the best known worst-case upper bound fir randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2 - 2/(k + 1))(n) up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481(n) up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:69 / 83
页数:15
相关论文
共 23 条