Evgeny Dantsin, Alexander Wolpert

Recently Schuler \cite{Sch03} presented a randomized algorithm that

solves SAT in expected time at most $2^{n(1-1/\log_2(2m))}$ up to a

polynomial factor, where $n$ and $m$ are, respectively, the number of

variables and the number of clauses in the input formula. This bound

is the best known ...
more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>