An Improved Algorithm for Sparse Instances of SAT

Sanjay Jain, Tzeh Yuan Neoh, Frank Stephan

We show that the CNF satisfiability problem (SAT) can be solved in time $O^{\ast }(1.1199^{(d-2)n})$, where $d$ is either the maximum number of occurrences of any variable or the average…