Sven Baumer, Rainer Schuler

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 >>>

Kazuo Iwama, Suguru Tamaki

This paper presents a new upper bound for the

$k$-satisfiability problem. For small $k$'s, especially for $k=3$,

there have been a lot of algorithms which run significantly faster

than the trivial $2^n$ bound. The following list summarizes those

algorithms where a constant $c$ means that the algorithm runs in time

more >>>