Improving a Probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs

摘要

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT) is a well known NP-complete problem and the development of faster (moderately exponential time) algorithms has received much interest in recent years. We show that the 3-SAT problem can be solved by a probabilistic algorithm in expected time 0(1,3290"). Our approach is based on Schoning's random walk algorithm for k-SAT, modified in two ways.