Abstract:
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 O(1,3290^n). Our approach is based on Schoening's random walk algorithm for k-SAT, modified in two ways.