We consider worst case time bounds for NP-complete problems
including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.
Our algorithms are based on a common generalization of these problems,
called symbol-system satisfiability or, briefly, SSS [R. Floyd &
R. Beigel, The Language of Machines]. 3-SAT is equivalent to
(2,3)-SSS while the other problems ... more >>>

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).
more >>>

This paper establishes a randomized algorithm that finds a satisfying assignment for a satisfiable formula $F$ in 3-CNF in $O(1.32793^n)$ expected running time. The algorithms is based on the analysis of so-called strings, which are sequences of 3-clauses where non-succeeding clauses do not share a variable and succeeding clauses share ... more >>>

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, Schöning proved ... more >>>