随机k-SAT问题的回溯算法分析

通过研究搜索树的平均节点数,分析了回虎法求解随机ｋ－ＳＡＴ问题的平均复杂性,结果表明：找到实例所有的解或证明其无解所需的平均节九随变量数ｎ的增加而指数增长;随着ｒ的增大,求解将变得越来越容易,而且当ｒ趋近于无穷大时,以ｎ为指数。平均节点数的底数将无限地趋势于１。     

随机k-SAT公式不可满足性VS最小k-击中集

给定一个k-SAT实例F,将作用于公式F得到随机k-SAT实例F′.在随机扰动模型M(m; n; k)下,随机k-SAT实例F′的若干性质.并证实当子句密度足够大时,随机k-SAT实例F′的不可满足性判定可以归结为最小k-击中集问题的求解.     

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

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, Schöning (1999) proved that a close algorithm for k-SAT takes time (2−2/k)ⁿ up to a polynomial factor. This is the best known worst-case upper bound for 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))ⁿ 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ⁿ up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.